Para el tema de los 4 datos por fila, puedes apoyarte usando la función
array_chunk, la cual separa un array en una cantidad A de B elementos.
Código PHP:
Ver original $array[] = $row["campo"];
foreach ($nuevoArray as $dato)
echo implode(' - ', $dato) . "<br />";
Esto me daría un resultado similar al siguiente:
Código HTML:
Ver originalA - B - C - D
E - F - G - H
I - J - K - L
Y lo mejor de todo es que si en la última fila hay menos de 4 elementos, imprime los que estén y así no nos complicamos por que debamos imprimir sí o sí 4 elementos por fila.
Para la paginación, te recomiendo leer
este tutorial, me ha sido de gran ayuda.
Un consejo más; múdate a la extensión
MySQLi porque la extensión
MySQL ya quedó obsoleta en las versiones más recientes de PHP.
Saludos