FWIW, autotools scales reasonably well. It only really falls over speed-wise when you start using things like gnulib, which because they test for every bug you can possibly imagine tend to take minutes to run a multimegabyte configure script.
The actual build, well, since cmake generates makefiles, the problem must be something other than cmake-versus-GNU Make. And it is. Firstly, a lot of projects, especially older projects, are rife with recursive make, which the advent of parallel compilation has made particularly clear was a bad idea from the start. But nonrecursive makefiles aren't hard to write with Automake, even for larger projects (see e.g. ImageMagick for an example). The payoff is just relatively low for the work that needs doing. The second problem is Libtool, which thought it is much faster than it was, really works at the wrong level: it should be part of Automake, so that the generated makefiles directly contain the appropriate magic incantations to generate shared libraries. Unfortunately if you fix that you break the people who are running Libtool directly, and those were its original user base: Automake integration came later.