Versions of CGI.pm later than 3.11, http://search.cpan.org/~lds/CGI.pm-3.11/ which was released 3 Aug 2005, causes lots of problems https://lists.webarch.co.uk/pipermail/mkdoc-dev/2006-April/000323.html with the way web addresses are constructed in MKDoc.
Until MKDoc is fixed to work with later versions of CGI.pm it is necessary to use 3.11 or older.
It is easy to manually install this version (necessary on distros like FC5 which come with a later version of CGI.pm):
wget http://search.cpan.org/CPAN/authors/id/L/LD/LDS/CGI.pm-3.11.tar.gz tar -zxvf CGI.pm-3.11.tar.gz cd CGI.pm-3.11 perl Makefile.pm make make test sudo make install
Or you could use the FC5 CGI.pm RPM which is avaliable from this repo: http://rpms.mkdoc.com/#fc5
wget http://rpms.mkdoc.com/pub/apt/fedora/linux/5/i386/RPMS.mkdoc/perl-CGI.pm-3.11-8.noarch.rpm sudo rpm -Uvh perl-CGI.pm-3.11-8.noarch.rpm
If yopu use the rpm you will need to reinstall it after updated versions of perl are installed, (there was a update in mid June 2006: http://lwn.net/Articles/187403/ ):
rpm -e perl-CGI.pm yum install perl-CGI.pm