Now you've stumped me. There's a kabillion ways to list 'em with UTW, but I don't think that's one of 'em.
It actually has a format very similar to that one, called "htmllist". A simple one to do this would be:
<?php UTW_ShowWeightedTagSetAlphabetical("htmllist", $limit); ?>
would be awfully close to what he wants.
Still, the count in parenths is missing. But, UTW can do Custom Formats easily enough. So this would work:
$format = array (
"none"=>"<li>" . get_option('utw_no_tag_text') . "</li>"
echo $utw->FormatTags($utw->GetWeightedTags("tag", "asc", $limit), $format);
UTW is powerful. Read the help that comes with it, it's got a lot of functionality in there.
BTW: In both of those examples, $limit should be replaced with the number of tags you want to show on the page, as a maximum. It can be arbitrarily large. Leave it out and the default is 150. Set it to zero and it doesn't implement a limit at all, going for as many tags as you actually have.
Anyway, the short version is that there is absolutely no reason he couldn't do this with Tags. It would be simpler to adminster as well, it wouldn't overload the system with all these categories, and yes, he could even keep the existing categories by converting them to tags. The modifications would be minor, at best. The change in behavior for new posts would be trivial, since you can just type in Tags or select them from the tag list on the posting page. Multi-word is not a problem as well.
Now, this all begs the question of why you'd want such a huge list of categories/tags on the page. I closed the page before it finished loading that gigantic list. But then I'm not here to judge. To each his own. :)