Te recomiendo 100% utilizar la clase phpPaging que ahorra un monton de trabajo a la hora de paginar , es sencillo de utilizar y lo hace por url.
http://phppaging.phperu.net/
Por ultimo hace tiempo que no lo utilizo y parece que no se actualizado desde 2008, la paginacion final queda identica al modo en que trabaja oscommerce.