Можно было бы подать заявку на удаление, но такой объем вы всю жизнь будете отправлять. 
Думаю, тут ничего не сделаешь. Я бы поставил редирект со всех этих страниц на главную, ну и корень проблемы сначала нужно исправить.

Еще, нужно продумать хорошо перелинковку, карту сайта добавить, заказать прогончик можно для ускорения переиндексации

PS. На самом деле, на 99% уверен, что позиции у вас падают не только из-за этих битых ссылок. Явно есть и другие проблемы

Цитата
WGN пишет: Цитата Анастасия Бабахина пишет: так еще и вирус на сайте появился Так а вирус удалили полностью, и у вас что на хостинге разве антивируса бесплатного нет?

Вирус удалили, но страницы, которые он сгенерировал проиндексированы

А как страницы сгенерированые вирусом отображаются в поиске Яндекса?

Может действительно поставить редирект на главную и увидеть в действии вируса несомненный плюс? 2 млн. страниц в поиске это же нифигасе.

Анастасия Бабахина, По хорошему вам нужно очистить базу данных от этого мусора, зачем его тянуть за собой. Страница отдаёт 404 значит они выпадут из поиска рано или поздно, Яндекс у меня до полугода около 20000 страниц пережевывал 404 кодом ответа.

Да уж, от такого вируса долго будете чиститься. Лихорадить пациента пол года еще будет как минимум.

Цитата
Thom333 пишет: Тут надо кардинально

отличное решение, ТС срочно делайте то, что вам посоветовал этот пользователь