Paul was never billinaire. He got ~300M from selling vk.com. Spent ~100M in first year. Spending on telegram's servers only is ~1M/month and telegram is 48+ months old. So he already spent almost half of his money.
I doubt that their operations costs are $1M per month. They should be 1/10th that amount. If you're spending that much, you are being robbed by employees or providers. This number is simply not believable by anyone who has experience running a large datacenter operations organization.
Yes, we are always wondering how it is possible. But you need to understand that telegram rolled not only their own crypto, but their own DB, PHP compiler and so on. Everything is written in C++.
To solve one of the earliest DDOS attacks telegram's team take their servers put it on the track and install them to other DC. This is insane.