A question, In your most complicated PowerApps how many screans you have in a single PowerApp, How many datasources are connected? How many formulas roughly per screen and how you describe your PowerApp performance vs. these factors?
There's no simple answer to that question. If application users will run the app on older or lower end mobile devices then that will enforce harder limitations.
Generally, the number of screens and number of data sources used does not affect the performance directly. For example, if you have many screens but load them one-by-one (imagine a survey type app) then this will not affect the performance as hard as having lower number of screens but also having rules or formuals that affect multiple screens at the same time.
Same applies to the number of data sources. Having a large number of controls referencing different fields from a low number of sources may be worse than having a higher number of data sources, each referenced by data controls on a certain screen.
Generally, there many ways to optimize your application (such as use a shell app that loads other apps, or pre-load the data sources to collections) but I would suggest to start with a "Proof of Concept" and to evaluate the performance on target devices.
My suggestion is to create a Proof of Concept (PoC) application that would emulate the intended funcionality in order to evaluate the performance. Dealing (Searching, Filtering and etc) with 10,000 (or 1M) entities is not an issue as long as you're not intending to load more that the maximum allowed records at a time (500 by default which can be increased to 2,000). You could bypass that limitation by loading the data in batches but hopefully you don't need to do that.