Ese paginador(
http://objetivophp.com/?p=183) que utilizas es independiente de Mysql, lo mismo podrías paginar un arreglo.
Lo único que debes hacer es por separado la consulta de ella extraes la cantidad de registros y se los pasas al paginador.
http://objetivophp.com/wp-content/up...orFullText.zip aquí tienes un ejemplo aunque el paginador es mas antiguo y utiliza una clase para generar la consulta.
Saludos