I think you can probably accomplish this easiest with the Force.com IDE. You could modify the package.xml to include new directories and place the reports in the new directory. Create a project in the IDE to download the reports and check out the package.xml for that project.
I'm not sure if you could get rid of the old hierarchy with the destructiveChanges.xml approach from the IDE, so you might have to do that one manually.
I think you can probably accomplish this easiest with the Force.com IDE. You could modify the package.xml to include new directories and place the reports in the new directory. Create a project in the IDE to download the reports and check out the package.xml for that project.
I'm not sure if you could get rid of the old hierarchy with the destructiveChanges.xml approach from the IDE, so you might have to do that one manually.
Hope this helps.