I was working in an organization that developed a big network switch, with a large C++ application running on it whose non-recursive Makefile took 30 seconds just to load and parse all of the include makefiles throughout the tree, before actually building anything.
Half a minute of waiting just waiting for that second that it then takes to recompile a single .cpp to a single .o and link everything.
I got tired and added a "make --dump" option which used the GNU Emacs undump code to dump an image of make with all the rules loaded from the Makefile. Then "make --restart" would instantly fire off the incremental rebuilds. (Of course, any changes to the makefiles or generated dependency makefiles required a new --dump to be taken to have an accurate rule tree.)
Another idea would be just to add a darn REPL to make, so you can keep it running and just re-evaluate the rule tree.