Sua `query` possui inconsistências (como o `LIMIT` no `COUNT`), porém sem dados para uma resposta mais elaborada só posso sugerir o seguinte:

Crie um índice para a sua tabela:

    ALTER TABLE categoria ADD INDEX categoria_index (tbl_pai);

Mais informações na resposta da pergunta [**Índices em consultas no MySQL**][1] e [**Para que serve o índice INDEX no MySQL?**][2].

  [1]: https://pt.stackoverflow.com/a/32072/59479 "Índices em consultas no MySQL"
  [2]: https://pt.stackoverflow.com/a/193305/59479 "Para que serve o índice INDEX no MySQL?"