У меня была такая проблема. Долго гуглил по этому поводу, в итоге через родной интерфейс мегафона так и не получилось.
Настроил новое соединение через System Preferences -> Network.
Там в списке есть модем: я указал номер телефона *99#, сохранил и нажал connect.
Точно не помню, возможно что то ещё пришлось прописать в параметрах подключения, но уже не помню.