If I recall correctly, DKIM setup is simply publishing the public key as a txt DNS record under your domain. Whoever has the fitting private key can then sign emails on your behalf. The cloud email host can without problem generate a new pair for every domain. So the "upload it's own DKIM key" is essentially creating a pair for you and telling you to set the public key as a certain DNS text entry. Pretty straightforward. Stopping the cloud provider to sign emails for you is also as simple as removing the DNS entry from your domain.
> I'm assuming nobody will provision infrastructure per tenant due to scale and cost
Actually, these services are available at a premium.