Eu finalmente tive tempo de rever este projeto e por causa da perfeição queria postar o que acabei fazendo. O problema original com o DELETE FROM demorando tanto, acredito, está relacionado a como eu estava especificando linhas a serem deletadas. Eu estava usando uma declaração semelhante a
DELETE FROM table WHERE starttime < 20150101 limit 200000;
O campo de hora de início é, na verdade, um DATETIME. Acabei criando uma nova tabela usando
CREATE TABLE new_table LIKE existing_table;
e, em seguida, alterando o mecanismo da nova tabela
ALTER TABLE new_table ENGINE=InnoDB;
e, em seguida, renomeie
RENAME TABLE existing_table TO old_table, new_table TO existing_table;
Depois disso, precisei obter 6 meses de dados da tabela antiga para a nova tabela
INSERT INTO existing_table SELECT * FROM old_table WHERE starttime BETWEEN DATE_SUB(NOW(), INTERVAL 6 MONTH) AND NOW();
Obrigado Martin pela sugestão. Sou novo no serverfault, por isso não sei como marcar o comentário dele como resposta.