Count queries, indexed or otherwise, are slow due to the fact that MongoDB still has to do a full b-tree walk to find the appropriate number of documents that match your criteria. The reason for this is that the MongoDB b-tree structure is not “counted” meaning each node does not store information about the number of elements in the node/subtree.
The issue is reported here https://jira.mongodb.org/browse/SERVER-1752 and there is currently no workaround to improve performance other than manually maintaining a counter for that collection which obviously comes with a few downsides.
Also, note that the db.col.count() version (so no criteria) can take a big shortcut and doesn’t actually perform a query hence its speed. That said it does not always report the same value as a count query that should return all elements (it won’t be in shared environments with high write throughput for example). Up for debate whether or not that’s a bug. I think it is.
Note that in 2.3+ a significant optimization was introduced that should (and does) improve the performance of counts on indexed fields. See: https://jira.mongodb.org/browse/SERVER-7745