If you're using MyISAM tables, it does not hit performance. MySQL caches number of rows in MyISAM tables. This is why it is able to instantly answer COUNT(*). In this case, MySQL would simply read number of rows in the table from stored value.
[EDIT]: From MySQL Performance Blog:
For InnoDB: If you have query like SELECT COUNT(*) FROM IMAGE WHERE USER_ID=5
this query will be executed same way both for MyISAM and Innodb tables by performing index rage scan. This can be faster or slower both for MyISAM and Innodb depending on various conditions.
In real applications there are much more queries of second type rather than first type so it is typically not as bad problem as it may look. Most typically count of rows is needed by admin tools which may show it in table statistics, it may also be used in application stats to show something like “We have 123.345 users which have uploaded 1.344.656 images” but these are normally easy to remove.
So remember Innodb is not slow for ALL COUNT() queries but only for very specific case of COUNT() query without WHERE clause.
Also interesting read for you: