to zalezy.
Jeśli zapytaniem pobierasz ileś tam rekordów i chcesz sprawdzic ile ci pobralo, to mysql_num_rows() jest jak najbardziej ok.
Jeśli zaś chcesz zliczyć całkowitą liczbę rekordów a pobrać tylko część z nich to mysql_num_rows() tu się nie nada. Zeby użyć mysql_num_rows musiałbyś pobrać wszystkie rekordy. No a to bardzo nie optymalne - masz np. w tabeli miliard rekordów i pobrać je wszystkie tylko po to by je zliczyc to bez sensu.
Liczbę rekordów ma ci zwrócić sama baza. W tym celu wykonujesz zapytanie:
SELECT count(*) FROM tabela
A następnie pobierasz wynik tego zapytania standardowo przy pomocy mysql_query() oraz mysql_fetch_array();