Due to popular demand (well, one, but who's counting;-) I extended my HotCat JavaScript tool so it can add categories on the upload page. As on "normal" pages, it enables you to see if a category exists, and makes suggestions for other (more specialized) ones.
Try it: http://commons.wikimedia.org/wiki/Special:Upload?withJS=MediaWiki:HotCat.js
The categories will be added when you click the upload button; until then, you can still modify/remove categories.
Cheers, Magnus