My largest Middleman site has about 5000 pages, plus large numbers of images, and takes a noticeable amount of time – maybe 10-15 minutes – to rebuild on an 8GB Linode VM. I would think that a million page site could be pretty slow to rebuild; hours if not days. During the build process, Middleman creates a complex data structure called the sitemap, which loads at least some information about every page on the site. A sitemap with a million entries would probably have significant memory requirements (understatement!)
You might want to take a look at Hugo, which is a static site generator written in Go. I’ve played around a little bit with Hugo, and while I haven’t used it yet for any major projects, I can confirm that it is extremely fast.