Have you ever used or heard of PSP Content Manager 1.8 before?
http://pspupdates.qj.net/PSP-Content-Manager-v1-8/pg/49/aid/100606
It's a handy PC app that allows you to scan your PSP (via a USB hookup) for homebrew, and sort the icons, all with a few mouse clicks.
Two caveats:
1) The app is pretty ancient and hasn't been updated to support newer CFWs (and thus, the newer folders that go with it). That's easily fixed.*
2) The app doesn't recognize CAT_ folders, so if you want to sort your game icons, you need to remove them from their CAT_ folder locations and place them back in their normal/expected locations. After you use this PC app to sort the icons, you can place them back in their respective CAT_ folders and they'll keep their new icon order.
*You can type up a Windows XP .reg (Windows Registry) file to "patch" PSP Content Manager to work with newer CFWs. I'll list below the two newest .reg files I've whipped up.
Open up Notepad (or whatever) and create a new file called CFW5XX.reg (or similar).
Cut and paste the following into that .reg file, save, and close it.
Windows Registry Editor Version 5.00
[HKEY_CURRENT_USER\Software\PSP Content Manager\Setting]
"CFWName"="5.00 M33"
"CFWFolder"="GAME5XX"
Double click on that .reg file in order to "patch" PSP Content Manager for 5.00 M33-x.
5.50 Gen-B uses the same folders as 5.00 M33-6, so technically a new patch isn't required. If, however, you'd like PSP Content Manager to mirror Gen CFW, then you can paste this instead:
Windows Registry Editor Version 5.00
[HKEY_CURRENT_USER\Software\PSP Content Manager\Setting]
"CFWName"="5.50 GEN"
"CFWFolder"="GAME5XX"
Either way, once you have PSP Content Manager up and running, sorting the actual CAT_ folders is deceptively simple. However, first I recommend connecting the PSP to your PC via USB, enabling USB mode, and launching PSP Content Manager just to get familiar with it. The tab you're looking for is the far-right tab.
If you used one of the registry patches I quoted above, then the tab will be named 5.00 M33 or 5.00 GEN. The name isn't really too important. If it lists something WAY older, though (such as 3.30 OE, for example), then you didn't properly patch it, and the app will probably not recognize all of your CFW folders, limiting functionality somewhat.
Keep in mind that if you have your homebrew sorted in CAT_ folders, then they won't all show up in this view, and you might get a ton of corrupt icons instead. I wouldn't fuck with things too much at this point.
Once you're comfortable with navigating the program, and would like to use it in an unintended way to sort your categories, continue reading below:
a) PSP Content Manager will pick up on all of the CAT_ folders listed under GAME, GAME150, or GAME5XX, so you don't need to do anything with those for now.
b) If you'd like to include your ISO category(ies), then you'll have to move them to one of the aforementioned folders (I used GAME5XX, since it's always empty for me). The CAT_ folders you want to sort can either be empty, or not. It makes no difference.
c) Connect your PSP to your PC via USB, enable USB mode, and launch PSP Content Manager. Click on the right-most tab to list all of your homebrew.
d) Chances are, not much will show up beyond "corrupt" icons sharing the folder names of your various categories (CAT_ this and CAT_ that). The program should also report that no eboots were found.
e) Simply drag and drop these corrupt icons into the order you the categories to show up in your XMB, and hit Apply Sort.
That's it.
Pro-tip: Move your homebrew/emulators/games/apps/ISOs from their CAT_ folders back to their natural folders and reload/refresh this application. If you proceed to the right-most tab again, you should see all of the games and whatnot show up. Drag and drop them into the order you want, Apply Sort, disconnect, and move your goodies back to their CAT_ folders.
Now, not only will your categories be sorted, but the goodies stored within those categories will ALSO be sorted.
It's a bit of a hack-y workaround, but it works rather well and the GUI interface is rather functional. I definitely wouldn't mind seeing a more modern successor app (either for the PC or one that functions from the PSP itself) to replace this. Preferably one that also supports the CAT_ folders.
Alas, I've yet to find one PSP icon-sorting app that doesn't break with the CAT_ folders, let alone one that could sort the CAT_ folders as well. Before this awesome Game Categories plugin, I used to use PSPFiler (PSP app) to PSP Console (awesome PRX plugin) to sort my homebrew icons.