Uma dica de um amigo salvou o dia. Esta parece ser a maneira mais rápida de realizar a tarefa:

1. Crie uma nova tabela com estrutura de colunas idêntica à original com a adição de uma coluna de incremento automático.
2. Adicione os dados da tabela original à nova usando INSERT INTO ... SELECT ... ORDER BY
3. Excluir a tabela original

Fez 9 milhões de linhas em 7 segundos.