glibc's malloc() is known to be lackluster under parallel workloads. Alternatives do perform better in certain circumstances, but profile before making the switch -- your situation might not be one of them.
It's possible to inject tcmalloc into an executable using Linux's preloader, too, without recompiling[1].
I'm quite surprised that idTech4 was using _any_ malloc implementation aside from the initial allocation of the memory pool that it would use for its actual runtime allocator.
It actually does use it's own heap allocator, with some additional allocators built on top of it. I don't know if it also uses the system / libc allocator for anything, but I'd be surprised if it did.
Aside from glQuake (which used a custom allocator for most of the game, but used malloc quite often in the GL renderer), all of id's other engines used custom allocators for everything.
Edit: just skimmed the white paper. They were talking about the custom allocator which was, of course, not thread safe, because it was designed for a single threaded game engine. Replacing that with an allocator designed for parallel usage (tcmalloc for example) would have helped, but so would having separate allocation pools for different threads (which you might do for a game engine designed for multithreading). Instead, they made the allocator thread safe, using their tool to analyze it, and then sprinkling it with mutexes. That would probably be why it was a bottleneck.
Even under single-threaded applications, with a custom allocator that suits your workload, it's possible to get significant speed boosts over the system malloc. One of the assignments I enjoyed back in college was writing a memory allocator. By the time I was done optimizing (including replacing all structs with raw pointer arithmetic using #defines), IIRC I was getting over 10000 single-threaded allocations per second vs. ~3000 from malloc().
It's possible to inject tcmalloc into an executable using Linux's preloader, too, without recompiling[1].
[1]: http://gperftools.googlecode.com/svn/trunk/doc/heapprofile.h...