I agree with all of these comments: CGI itself is slow, CGI.pm probably lacks from an initial design that tried to cram too much features in a single module, and it is possible to write a much faster module by leaving out the HTML generation parts of CGI.pm. This does not detract from my initial point though: sometimes during the life of the module (I would guess around version 2.0, it's hard to tell from the Changes file) Lincoln started optimizing it, which lead to the current code. In short the code is not hairy because the author can't code properly, it is hairy because the author knows what he is doing and he does hairy things in order to provide its large user-base with as much speed as possible, while staying backward compatible with older versions (how's that for short! ;--).

I would add that an other reason to use a module is the support it gets from its author. In this case it has been really good, just look at the Changes list. I really appreciate the fact that CGI.pm generate conformant XHTML for example.