The WPEssence Bulk Categories plugin allows for easily creating multiple categories at once, including slugs and category parents.
This is a superb plugin that WILL save you time when it comes to adding categories.
However, it would be ideal if could EDIT existing categories, as well as just add new ones. You can end up adding 100s or 1000s of new categories, and then when you reconsider your category structure, you have to delete or amend them one by one. Would be great if the plugin allowed you to access the saved data and then edit them in bulk!
Also, the plugin only allows you to enter the name and slug of each new category added, but not the description of the new categories. This will be fine for most users most of the time, but is restrictive for those of us who requires descriptions too!
Have suggested the above to the author, and hopefully might be available in a future version, but for now this is still a 'must-have' plugin for those of you who add lots of categories!