Под сотню миллионов держит спокойно, но конечно же таблица жестоко оптимизирована для конкретных достаточно простых запросов. InnoDB.
Переходить на другую СУБД, скорее всего, не стоит. Стоит измерить, насколько плачевная ситуация сейчас и можно ли ее изменить. Проанализируйте, какие запросы идут к таблице, насколько быстро они работают, какие основные операции идут (вставка-чтение), нет ли из-за этого забавных эффектов (например, блокировки на MyISAM и на InnoDB сильно отличаются), все ли индексы стоят, нет ли лишних индексов, нельзя ли их уменьшить и т.д. После этого будете принимать решение. Если сейчас у Вас 1 млн, можно забить тестовую базу на 5 млн и посмотреть, сильно ли изменился расклад.