Mira en los comentarios de los usuarios en
www.php.net/mysql_num_rows todo lo que hablan de SQL_CALC_FOUND_ROWS y FOUND_ROWS().
Personalmente lo que hago es un select count(*) from tabla where loquesea . No sera ni lo mas optimo ni lo mas exacto, pero para la mayoria de los casos es mas que suficiente.