At my previous job I did exactly this. We were in the 500 tenant range, but once you get above 10 or 20 the automation part makes the actual number much less important.
Assuming that your hardware can handle backing up 10,000 databases in a sufficient time, and that all 10,000 aren't having significant enough activity to overwhelm your server with or without backups, the next step is to automate the process in general. The nice thing about this model is that if 10,000 databases end up overwhelming your server, it is much easier to move half of them to a second server and point your applications at the right instance depending on the tenant, than it is to try and rip half of the data out of a single database. Do you have some that are in FULL and some in SIMPLE, or are they all in the same recovery model?
We had priorities. So a table to hold the tenant information (in my implementation there were many more columns, but this should be the basics):
CREATE TABLE dbo.TenantBackups
TenantID INT PRIMARY KEY,
And then a history table (again, more to it in the actual system, but for the purposes of the question):
CREATE TABLE dbo.TenantBackupHistory
TenantID INT, -- FOREIGN KEY,
BackupType TINYINT, -- lookup for FULL, LOG, RESTORE_TEST
Status NVARCHAR(1000) -- almost always NULL but held true "exceptions"
So now the job(s) could run through the tenants, ordered by priority, and perform backups. We actually had separate jobs for priority 1s vs. priority 2-5.
We tested priority 1 tenants nightly by restoring their full backups on a backup server. We also picked 20 random databases from the other priorities each night to test their restores as well. There were alerts etc. configured of course so that failures were immediately known, and if the exception was outside of our normal retry/error handling the Status column would contain information.
We also used Event Manager (made by SQL Sentry who, for full disclosure, now employs me) to chain jobs so that we didn't have to worry about scheduling a buffer and trying to predict when the backup jobs would finish. For priority 1 databases we didn't bother to wait for the backups to finish as a whole; we had a background thread that would wait for each individual full backup to complete and then would immediately pick it up off the queue and start the copy/restore test processes. For priority 1 tenants we also used the restored copy as a reporting offload - for any reports that were interested in data before today (which was most reports), they could run off the copy, because the only thing it was missing was today.
For full recovery tenants (not all customers required point-in-time), the log backup jobs could easily check the history table to see if a backup of any kind was already in progress. But of course error handling and retry logic was implemented all around.
I know these are very generic descriptions but I hope they point you in the right direction. Let me know if you'd like me to expand on any details.