Considering it is an exploration achievement, I doubt you will actually be interacting with a merchant as the first step. You probably find something, then take it to a merchant.

The merchants, beggars, and people for the keeper of the flame achievements all spawn along roads in each zone, and all of them share spawn points so if one is there you'd have to wait awhile to see if one of the others spawns. They DO NOT share spawn locations with M'aiq the liar. Also Intimidate will be required for the merchants to get bandits heart to track.

Hmmm. Was wondering about the random beggars. When I give them coin, I hear a sound like I achieved something, but no message on what it is. I am wondering if they are part of an upcoming thief's guild deed or such. One was in Audiron area, saying he had been robbed by bandits. First character gave him coin, got the sound. On second character, I chose asking him to take me to the bandits, as it sounded like a quest starter. He insulted me, then turned untalkable to.

EDIT - Did some googling, found out more. Is it a bug that there is no text info when I give money to a beggar? You get it when you find lorebooks, locations and such.