Under your site's Tools > Import
menu there is a plugin you can install called Categories and Tags Converter, which once installed will give you control over how to handle categories you might want to convert.
This is a relatively painless process in the 3 times I've used it, but I never concerned myself with migrating older urls. If that's a concern, and the "slugs" for category are the same, and you're running under Apache, some .htaccess
directives for the individual categories should do the trick. So, assuming you have urls like:
http://example.com/archive/category/foo
http://example.com/archive/category/bar
And want to change them to:
http://example.com/archive/tag/foo
http://example.com/archive/tag/bar
You would add directives for each one in your .htaccess
file, like so:
Redirect permanent /archive/category/bar http://example.com/archive/tag/bar
Redirect permanent /archive/category/foo http://example.com/archive/tag/foo
Now, that presumes that you want them redirected, and none of your blog authors are going to be adding those categories back!
But generally, this would be the approach that would work.
If you're at all concerned with losing data when you alter content, BACK UP YOUR MYSQL DATABASE. Sorry, I had to yell that. :-) And if it goes haywire then simply restore your database.
If you have linked to those old urls in your content, they'll redirect fine. But you could also run WordPress Search and Replace plugin, which facilitates a migration like that, but again, mind backups especially with the Search and Replace plugin, since it makes its changes with no backup.