Executing query against Azure SQL db using Linked server takes hours
I think you're running into a key limitation of distributed queries (e.g. four part notation).  As per this MS blog post:


  data for remote queries are collected from the remote servers,
  scrubbed locally, combined together and presented to end user as single record set


Basically the source tables in their entirety are trying to get pulled over the linked server and all the joins and filtering are happening locally.  When you're not working with millions of records this is often transparent, but when you include large tables you can immediately feel the pain.

In your situation, I suggest you push a copy of the SAExMark.dbo.RealGreenZipCodeData table up to your Azure DB and then run this UPDATE statement from a connection made directly to the AzureDB.  If you need to initiate the process from a different server, stuff the update into a Stored Procedure in the Azure DB and then execute the SP remotely.

Alternatively, if you don't want/can't push that table to Azure, you could convert the query to utilize OPENQUERY for all the remote join operations.  This will quickly get ugly, but it's possible.  OPENQUERY will force execution of whatever query you pass to it remotely, therefore allowing the join logic against that large table to be done remotely so only whatever records are returned from that query travel back over the linked server.  These would then be joined against the local copy of the SAExMark.dbo.RealGreenZipCodeData to identify what records in AZUREDB.dbname.dbo.DealerMedias would need to be updated.  I really don't like this approach just to update a table on a remote database, but it's an option.