One trick with counts is that you very rarely need a perfectly accurate count for that exact moment in time; doing an explain on an appropriate 'SELECT' and capturing the estimated number of rows returned by that is usually good enough in 98% of the cases.

When you do need an accurate count, phrasing the query so the results can be pulled exclusively from the table index is also usually good enough.