I won’t be surprised if this is one of those things that everyone knows, but it wasn’t intuitive to me the first time.
Say you just created a new Azure tenant foo with a credential called admin, and you’d like to grant permissions in that new tenant’s Active Directory to credentials from the Active Directory of your company’s existing Azure tenant called bar. You can’t log into the new tenant AD as foo/admin and add bar/joebagadonuts, because the foo AD doesn’t recognize the bar AD, and you can’t log into the bar AD as bar/joebagadonuts and add foo/admin because the bar AD doesn’t recognize foo. You need one before you can have the other, both directions. Got it?
The solution is to use neither of those accounts for the initial connection. Instead, bootstrap your AD connection by using a Microsoft account.
Azure AD has the capability to add Microsoft accounts (from hotmail.com, outlook.com and live.com domains, or any email address that you register as a Microsoft account). Take a Microsoft account you own like joebagadonuts at hotmail.com, and add it (ask to have it added) to the bar AD as a user. It doesn’t need any permissions there. Also add it to the foo AD with appropriate account administrative permissions. Log in to foo as joebagadonuts at hotmail.com and add the credentials you want from bar. You can then make bar/joebagadonuts an admin on foo if you’d like to get rid of the Microsoft account.
Postscript: You may be tempted to use the Microsoft account version of your work email address. I wouldn’t do that if I were you. Too confusing, and if I recall correctly there are situations where Microsoft’s login tools don’t give you the opportunity to disambiguate between your work and Microsoft account versions of the same resource name. If you don’t have an alternative Microsoft account, just go to outlook.com and create a new address for this purpose.