So, one tool I've found very useful with MediaWiki is cvs2cl:
http://www.red-bean.com/cvs2cl/
There's a Debian package, too ("cvs2cl"). This tool parses CVS log output to a nicely-formatted ChangeLog file.
It might actually be useful to ship the generated changelogs with MediaWiki releases.
~ESP