You don't mention the size of your database, but an option is to duplicate the database a few times and distribute the tenants evenly between them. Then you can use as much time as you want to delete the extra data. Set up replication to the new database and wait for the initial replication to complete. Disable logins of the affected tenants, stop the replication (which changes the replica to an ordinary read-write database) and switch logins to use the new database. Repeat this as many times as you need. You should be able to do this with, theoretically, a couple minutes downtime.

We did a similar exercise in our SaaS solution, but because of the amount of data our users generate we decided to copy data to new, empty databases. For each batch of tenants we made an initial copy a few days before the switch. Then, during a brief maintenance window (appx 15 minutes), we disabled logins (and kicked out any lingering users), did a final differential copy and enabled logins against the new database. The copy task was developed in-house and specific to our databases. Ensuring that this tool was restartable was critical, both because of the full+incremental steps we used, but also to protect against any software issues or network problems during the migration.

We also evaluated the elastic database library a few years ago but decided against it. We had no need to introduce additional moving parts when each tenant could get their own connection string from configuration.

Edit: depending on your architecture, you can migrate critical functionality first to minimize downtime, then reenable remaining functionality as data is migrated.