Incremental compilation, i.e. the ability to reuse cached outputs from prior compilation efforts, can significantly mitigate compilation cost issues because we usually edit only a small part of a program before recompiling.
Unfortunately, the granularity of 'modules' is not adequate for languages that use a lot of metaprogramming or compilers that perform many cross-module optimizations (such as inlining and constant propagation across abstract function calls).
So, I've been approaching this with the idea of supporting explicit memoization of functions via program annotations. This would also apply to compile-time functions, e.g. maintaining a persistent memo-table based on secure hashes of the functions and their parameters. Programmers could use this feature for metaprogramming (macros, templates, static eval, etc.). Compiler writers could use it within optimization passes.
I don't know how well it will work out, yet. I haven't gotten that far in my language implementation, so it's still just an idea. However, assuming it works out, this would suggest a functional paradigm - at least for the compiler itself - is a very good idea because we cannot conveniently take 'secure hashes' of or memoize mutable object graphs and inputs from side-effects.