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