I've written a couple of new perl scripts that I just submitted to my public perforce directory.  These scripts are designed to make restructuring files in your server easier by allowing you to use your standard file manipulation tools to move things around until you're happy with the result.  The files are located here:

//guest/jeff_grills/restructure/restructure_start.pl
//guest/jeff_grills/restructure/restructure_finish.pl

When you run the restructure_start.pl script, it grabs the list of files on your client using "p4 files //...#have", so it depends upon your client mapping and what you have sync'd/flush'd to your client.  It will use that information to create the entire hierarchy of directories and files in your current directory, but instead of each file having its normal contents, it instead has the depot name of the file which was used to create that file.

As mentioned above, you then use whatever tools you want (Windows Explorer, etc) to move those files around until you're happy with the final structure.  You can move files, duplicate files, and delete files.

Then, you run the restructure_finish.pl script.  This script will scan the modified directory tree, and for every file it finds, it will look inside that file to determine where it came from.  If the original depot location is not the same as the current file location, the program will emit a "p4 integrate source destination" command to standard output to integrate from the old location to the current location.  After that, the script will issue another "p4 files //...#have" command and look for each of those files in the new directory tree; if it does not find them, it will emit a "p4 delete file" command to standard out to remove that file.

I'd suggest capturing the output from the restructure_finish to a file, and then making a pass over that file to check for correctness.  Once you're satisfied, you can execute all the command in that file (in Windows, you can name the file with a .bat extension and execute it; in unix, you can source the file into your current shell, or execute it as a shell script).  Again, you should check the final result for correctness before submitting.

I hope this helps someone else out.  It sure made restructuring some files here a lot easier.