In the 1990 film the explanation is pretty clear: Quaid create his alternate persona and simply informed Cohagen of the plans that he made. That way even when Quaid had removed the hidden transmitter from his bead, Cohagen would still know that Quaid plan entailed him infiltrating the Resistance and eventually returning to Mars. This would have tracking him relatively easy as Cohagen had inside information about his plans.
Cohagen also employs operatives (such as Benny the mutant taxi driver) who keep track of Uade when he's on Mars. That way, even Quaid were to somehow figure out that his change of heart was really a ruse, there were already agents in place to track his movements and inform Cohagen as to where and later Kuato, leader of Mar's underground mutant resistance were located.
The 2012 film is is even easier to understand as there were only two places where Quaid could be: The UFB or The Colony. Since there is no space travel and the rest of the Earth was a poisoned wasteland, Quaid was either in one or the other and as shown Cohagen had agents in both. Also, it can be surmised from the later video showing Quaid and Cohagen together that Cohagen knew about the entirety of Quaid's plans in advance.
Side note: While it's clear in the Philip K. Dick source novel We Can Remember It for You Wholesale That Quaid's (in the novel his name is Quail) that some of his memories are clearly fabrications, both film versions are portrayed as straight recitations of the events which occur. In both film narratives, Quade is prevented from undergoing the Recall/Rekall memory process and, as such, is living out the events which unfold.