Uma coisa que pode estar atrasando o processo é o key_buffer_size , que é o tamanho do buffer usado para blocos de índice. Ajustar isso para pelo menos 30% da sua memória RAM ou o processo de re-indexação provavelmente será muito lento.
Para referência, se você estivesse usando InnoDB e chaves estrangeiras, você também poderia desabilitar as checagens de chaves estrangeiras e reativá-las no final (usando SET FOREIGN_KEY_CHECKS=0
e SET FOREIGN_KEY_CHECKS=1
).