I'm not familiar with nor do you show the basis of the class: Paginated.
But...
I can tell that if the class requires a full result set (as shown by your select statement) to operate properly, then it is possibly flawed and inefficient.
A proper pagination routine should be based on the page number requested plus the number of "pre-defined or user-selectable" results to be displayed per page.
i.e.
SELECT * FROM movies LIMIT 0,100
- or -
SELECT * FROM movies LIMIT 100 OFFSET 0
You could then use the page# requested to calculate the OFFSET.
i.e.
define("RESULT_LIMIT",100);
$page = isset($_GET['page']) ? (int) $_GET['page'] : 0; // ensure we get a numeric
$page = $page * RESULT_LIMIT; // set the page offset
$sql = "SELECT * FROM movies LIMIT $page OFFSET ".RESULT_LIMIT;
// Output pagination at top
// Output results in a loop or from a module...
// Output pagination at bottom
There are numerous pagination classes and functions available on the net that will work for you.
A little pagination helper that I've used a few times in the past can be found here:
php easy :: pagination scripts set
It has a fairly small footprint and easy to use.
There are three functions included that you can pick from that use different pagination styles.
There is also a css file included that will style the pagination output.
You'll probably need to tinker a bit with it.
But as stated, there are many other (and better) "paginators" available online.
Hope that helps.