Include related entry slug in URl
Assuming your store/brand field handle in your new channel is relatedEntryField, set your URL format when you're defining the channel section to:

{relatedEntryField.first().slug}-{slug}


That'll pull the slug from the first related entry, add the slug from your current entry, and populate your URL. 

As an aside, relational fields are always "arrays" even if there's only one so you need .first().