SELECT COUNT(*) FROM tablename parece fazer uma varredura completa da tabela.

SELECT COUNT(*) FROM tablename USE INDEX (colname) parece ser bastante rápido se o índice disponível for NOT NULL, UNIQUE e de tamanho fixo. Um índice não-UNIQUE não ajuda muito, se é que ajuda. Índices de comprimento variável (VARCHAR) parecem ser mais lentos, mas isso pode ser apenas porque o índice é fisicamente maior. Índices inteiros UNIQUE NOT NULL podem ser contados rapidamente. O que faz sentido.

O MySQL realmente deve realizar essa otimização automaticamente.