Jeśli zgadzasz się z szacowaną liczbą i po prostu nie chcesz zadzierać z uruchomieniem SHOW TABLE STATUS
z PHP, możesz użyć DB information_schema:
SELECT TABLE_ROWS FROM information_schema.tables
WHERE TABLE_SCHEMA = 'my_db_name'
AND TABLE_NAME = 'my_table_name';