I managed to open the 5th Region within my first 18 months of playing. I had one region that was very population heavy (Cactus Canyon, mostly Omegas), at 3.7m, my others were at 2.8m, 2.0m and 1.5m.
It needs a lot of RZs and good boost buildings (Regional Hot Spots are excellent for this). I borrowed my best buildings from my Capital and bought a lot of extras during Black Friday - my last 1m population was just from swapping things around to get the best population boost, one small area at a time.
Once you make it you don't need to keep it over 10m, you can redesign and focus more on aesthetics.