For the second query, the “count”, there’s an option to turn all counts off in List views, this usually helps for large databases. See disable_count_query here: https://docs.suitecrm.com/developer/performance-tweaks/
For the first one, please check your database indexes to see. I’m not very knowledgeable on this subject, but for someone with good DBA skills this should be straight-forward.
Finally - are you sure your database hardware is up to the task? Ensure the server is not starved for resources (memory, CPU, disk throughput) given the dimension of your database.
Thanks for the script, I will have a look! This could be done with Beans (instead of direct SQL) by calling the paginated search (get_list) instead of the get_full_list (like the Elastic Search indexer currently does 
). But I think your approach is also ok, I don’t see any problems with it.