As consultas de contagem, indexadas ou não, são lentas devido ao fato de que o MongoDB ainda precisa fazer uma caminhada completa na b-tree para encontrar o número apropriado de documentos que correspondam aos seus critérios. A razão para isso é que a estrutura b-tree do MongoDB não é "contada", o que significa que cada nó não armazena informações sobre a quantidade de elementos no nó/subárvore.

O problema é relatado aqui https://jira.mongodb.org/browse/SERVER-1752 e atualmente não há solução alternativa para melhorar o desempenho além de manter manualmente um contador para essa coleção, o que obviamente vem com algumas desvantagens.

Observe também que a versão db.col.count() (portanto, sem critérios) pode pegar um grande atalho e na verdade não executa uma consulta, portanto, é rápida. Dito isso, nem sempre relata o mesmo valor que uma consulta de contagem que deve retornar todos os elementos (não será em ambientes fragmentados com alta taxa de transferência de gravação, por exemplo). Em debate se isso é ou não um bug. Eu acho que é.

Observe que na versão 2.3+ foi introduzida uma otimização significativa que deve (e deve) melhorar o desempenho das contagens em campos indexados. Veja:https://jira.mongodb.org/browse/SERVER-7745