Сколько всего записей у вас в таблице?
Проиндексированы ли поля, по которым выбираются записи на удаление.
Если вы удаляете большую часть данных - возможно имеет смысл перенести только нужные данные в отдельную таблицу, удалить старую таблицу, переименовать новую таблицу в старую, построить необходимые индексы.