1) Сколько места будет занимать база с 1 млн подобных записей?
В текущих реалиях - незначительное. Грубая верхняя граница - 10Гб (плюс-минус пара петабайт).
Насколько тяжёлые будут запросы к выборке из такой большой базы?
Зависит от запросов.
Если база увеличится до 10 млн, то и длительность/тяжесть запросов пропорционально в 10 раз увеличится?
Прямой корреляции между размером таблицы и скоростью выполнения запросов нет, движущихся частей в этом процессе довольно много - это и индексы и структура самих запросов.
На какие параметры стоит обратить внимание при выборе хостинга/vps/vds под такую базу?
Для сферической базы в вакууме, с которой будет работать сферическое приложение в вакууме берите тот сферический VDS в вакууме, на который у вас хватает денег. Если он не будет справляться со сферической нагрузкой в вакууме, берите VDS мощнее. Live - Die - Repeat.
P.S.
Насколько тяжело работать с большой MySQL базой?
К вечеру начинает лапы ломить и хвост отваливается, но в целом - терпимо.