Split document library

By default, in SPO, the list view threshold is configured at 5,000 items as also mentioned in the comments here and indeed exceeding it can lead to unexpected scenarios such as the one you encountered.  

Try creating views where you filter the items by indexed columns and make sure to not exceed the threshold/per view. 

Also, you could also use a script for downloading all files or try to make use of the PnP module (there used to be a cmdlet that allowed you to download files in a library - you could check on that). :)

Using hierarchical folder structure is recommended when working with large lists. 
https://support.office.com/en-us/article/Manage-large-lists-and-libraries-in-SharePoint-b8588dae-9387-48c2-9248-c24122f07c59 

Root problem: you are hitting the List View Threshold (LVT) (5000 on SharePoint Online).

Tools like "Open in Explorer" and many other tools cannot cope with this because SharePoint blocks requests that consume too many resources. 

Do you want to keep the pictures in the same library? If so, downloading them and then uploading them into a folder structure will be quite cumbersome.

There are tools that can circumvent the LVT. For example SLIM Companion Explorer retrieves data in chunks. The tool mimics "Open In Explorer" in a browser. You can use the tool to move pictures to folders within the same document library or download all items. It also offers previews for images similar to File Explorer.

One feature may also be of interest to you: it is capable to extract metadata from images (and also other formats like emails, PDF, ..) during uploading and capture the values into SharePoint columns. This way metadata like date taken, GPS location, etc ... can be used in views.

Note: I am affiliated with the vendor.
Paul

Hi

Why not create a new site collection with a new library. Create your new information architecture in this new environment. You can test your new way of working here.

Then I would use a tool (perhaps ShareGate) to migrate the content to the new environment.

[edit] ...and once the migration is succesfull delete/backup your original content ;-) [/edit]

Please think your new information architecture (your folder structure as you suggest) through. Perhaps you did this already but just didn't mention because it was a bit off-topic.

Then I would suggest another tip.

Perhaps you can use cognitive services to auto tag the images for you! I've been googling a bit for an example and found this link:

https://gunnarpeipman.com/sharepoint/sharepoint-describe-tag-pictures/

Another tip:

Who are your content users? How do they use these images? How do they find the correct images?

Who are your contributers? Who is actually uploading the images? How can you help THEM upload the images in such a way that the content users can find the images quicker? 

#hopethishelps!