Las consultas de recuento, indexadas o no, son lentas debido al hecho de que MongoDB todavía tiene que hacer un recorrido completo por el árbol b para encontrar la cantidad adecuada de documentos que coincidan con sus criterios. La razón de esto es que la estructura del árbol b de MongoDB no se "cuenta", lo que significa que cada nodo no almacena información sobre la cantidad de elementos en el nodo/subárbol.
El problema se informa aquí https://jira.mongodb.org/browse/SERVER-1752 y actualmente no hay otra solución para mejorar el rendimiento que no sea mantener manualmente un contador para esa colección, lo que obviamente tiene algunas desventajas.
También tenga en cuenta que la versión db.col.count() (por lo tanto, sin criterios) puede tomar un gran atajo y en realidad no realiza una consulta, por lo tanto, es la velocidad. Dicho esto, no siempre informa el mismo valor que una consulta de recuento que debería devolver todos los elementos (no será en entornos fragmentados con alto rendimiento de escritura, por ejemplo). En debate si eso es o no un error. Creo que lo es.
Tenga en cuenta que en 2.3+ se introdujo una optimización significativa que debería (y lo hace) mejorar el rendimiento de los recuentos en campos indexados. Ver:https://jira.mongodb.org/browse/SERVER-7745
