I know it's unbelievable. But other personal experiences make me think they're probably right. I have written equivalent OCaml and C++ code where the C++ version were 5 times larger (both where optimized for clarity). In my day job, I routinely divide substantial portions of C++ code by 2 through light refactoring.
VPRI's miracle doesn't only come from the awesomeness of their ideas. It also comes from the awfulness of current systems. A full desktop in 20.000 lines may not be so small, if you consider that current ones are way too big.
Addendum: I omitted a rather important detail: while the STEPS project aims to build a full desktop system, along with networking, publishing, messaging, and programming capabilities, it makes no attempt be compatible with anything (except the hardware on which it has to run). It doesn't do HTTP nor HTML, for instance.