A los resultados que ya obtienes paginado .. aplica la técnica que describe esta FAQ:
http://www.forosdelweb.com/f18/faqs-php-530600-post240669/
Pero recuerda que "Paginator" o tu rutina de paginado en sí es completamente idependiente de lo que puedas hacer para mostrar los resultados que obtengas -por página-
Un saludo,