Try running make at the top of an AOSP tree, it takes about 60 seconds, and that part cannot be parallelized.
If you are looking for alternatives, have a look at http://martine.github.io/ninja/
But if you already have a huge mess of recursive make, it might be easier to port it to a non-recursive Android-like system then completely rewrite it with gyp/gn/cmake + ninja.
It would speed up your full build times; not sure what it would do to incremental build times. It is true that the Android.mk thing has a large startup cost. Then again, you're building a whole OS with one make invocation, which is kinda cool.