la idea es hacer una consulta de todos los registros y si ocupas mysql_num_rows() obviamente te dirá tu total de registros... no hay problema al consultar las dos tablas por separado.. aunque igual puedes hacer una sola consulta.. de hecho puedes consultar el total de registros desde MySQL (si es lo que ocupas)... date una vuelta por
www.mysql-hispano.org ... seguro encuentras lo que buscas.
Suerte!