There are several ways to approach multi-tenancy with Auth0, and which path you choose will ultimately depend on your use case.
This doc goes into detail about the various configurations: Multi-Tenant Applications Best Practices.
From what you have shared here, separating your tenants with Connections sounds like a fitting approach. Although, there are some limitations to this strategy. Namely, you will likely need an enterprise subscription due to the number of Connections you would be creating.
These types of setups often require a professional services engagement. I would suggest talking to our sales team to get that process started.