It was possible to upsert data using polymorphic relationships during bulk api.
In this case the Custom Object Relation__c had lookups to the Account object a__c and b__c and the account object had an external id z__c
So the csv column Headers used to upsert data in Relation__c as below:
Account:a__r.z__c
Account:b__r.z__c
This helped to upsert data to this custom object and associate the lookups to the accounts at the same time using external id fields on account, instead of using salesforce ids.
Similarly,
If you have lookups on the Account Object referencing other objects, then the relationship will be simpler, you don't have to include the name of the lookup object.
Account_Field__r.LookupObject_External_ID__c