Doxymacs is GPL, and the elisp in doxymacs.el is very simple, just a bunch
of tempo templates and helper functions. It has dependencies on W3 and
tempo.
Doxygen is also GPL, but considerably more complex. The installation notes
(
http://www.stack.nl/~dimitri/doxygen/install.html#install) mention
flex, bison, make, perl, qt, latex, graphviz, and ghostscript (the last 4
are output targets and are not requred to build).
Many or all of these are probably already installed on your Linux box, but
personally I opted for the binaries.
How complex is doxygen? Steve Y already has a package (eicq) which
builds and installs a helper app. Of course JDE does something
similar. So I don't see why it's un-doable. Several of us would like
to see T. V. Raman's Emacspeak packaged, too.
That would be so cool.