First let me say that this is not flame bait. I can only comment on Oracle, but these results should not be considered useful against any other database besides MySQL. I'll save the gritty details unless anyone wants to hear about them.

One issue that I've not seen mentioned here is whether the database lives on the same machine as the code you're executing. I'm assuming it does, or you have a very fast network, or you have a small set of data. This is because if you were running on another machine your query would have to return the result set over the network, which could take a long time depending on the size of your data. One million rows * 1kB is much larger than a single count of the rows.

Another optimization you may want to test out would be to try doing a SELECT COUNT(1) FROM TABLE WHERE BLAH this will return the same result as COUNT(*) but may run faster depending on what kind of optimizations are done. This can be faster because we're not asking the database to return rows from the table, just the count. An old oracle trick until they internally optimized COUNT(*)

HTH