The WPEssence Bulk Categories plugin allows for easily creating multiple categories at once, including slugs and category parents.
Enter the categories you want to add in the left textbox, separating different categories by newlines. You can assign categories to parent categories by entering the full category path, separating different category names by slashes (/).
Slugs will be automatically generated if they are not manually set, but it is also possible to enter specific slugs for each category. You can do this by putting the slugs in the right textbox on the lines of that textbox corresponding with the lines in the left textbox (for the category paths).
In the "Bulk Add Categories" screen, there are two textboxes. The left one is for the categories, and the right one is for the category slugs. The textboxes have line numbers, allowing you to easily choose the slugs for the right categories, even if you are adding a lot of categories at once. If you leave a line blank, the category with that line number will automatically generate its slug.
Parent and child categories are separated by a slash (/). If your category name contains a slash, such as "Audio/Video", you can use quotes to use that as a full name (so it won't get seperated as Audio -> Video).
Yes, as of version 1.1, the plugin allows you to create custom taxonomies as well as other built-in taxonomies such as tags. To create custom taxonomies, go to the Bulk Categories screen and select the taxonomy you wish to create at the top.
If you go the "Bulk Add Categories" screen, you can view an example by clicking on the example-link (under the "Example" heading).