Working with a large amount of files in a single folder?

I was really glad to find the WordPress Media Library Folders plugin today because it says that it allows to actually move media files into subfolders, but right now our WordPress Media archive has over 58.000 pictures in three folders. With such a high number of files the interface doesn’t even load. Same with the cPanel File Manager, takes forever to load and then crashes… The only option I can think of right now is using FTP to move the pictures into subfolders but that would break the links, wouldn’t it? Is there any way to better sort these pictures into subfolders to make them manageable?
Any suggestion is much appreciated, thanks!