Hi Bernd,
I ran into this very issue recently after having gone live with a new document library to store a large number of files that were being hosted on a different (and costly) cloud platform. Of course, during testing the Flow was working great (picking up newly created and modified files) - but as soon as I brought everything over (73k+ files in total) and 'turned the lights on' the trigger would no longer trigger!
Anyways, I was able to resolve it by turning on indexing on the 'Modified' column. Since I hadn't seen this documented anywhere (and I did a lot of searching), I went ahead and created a post to walk you through the process in case you need more detailed guidance. Here's the link:
https://www.ohthreesixtyfive.org/2018/03/microsoft-flow-overcoming-the-list-view-threshold.htmlOf course, if you have exceeded 20k items you'll need to trim it below that to be able to turn on indexing, but otherwise it should be pretty painless. Let me know how it goes!
Best regards,
Ramiro