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