The German chancellor also told the US president that America's National Security Agency cannot be trusted because of the volume of material it had allowed to leak to the whistleblower Edward Snowden, according to the New York Times.
Livid after learning from Der Spiegel magazine that the Americans were listening in to her personal mobile phone, Merkel confronted Obama with the accusation: "This is like the Stasi."
The newspaper also reported that Merkel was particularly angry that, based on the disclosures, "the NSA clearly couldn't be trusted with private information, because they let Snowden clean them out."
Snowden is to testify on the NSA scandal to a European parliament inquiry next month, to the anger of Washington which is pressuring the EU to stop the testimony.
In Brussels, the chairman of the US House select committee on intelligence, Mike Rogers, a Republican, said his views on the invitation to Snowden were "not fit to print" and that it was "not a great idea".
Inviting someone "who is wanted in the US and has jeopardised the lives of US soldiers" was beneath the dignity of the European parliament, he said.
He declined to comment on Merkel's alleged remarks to Obama. In comments to the Guardian, he referred to the exchange as "a conversation that may or may not have occurred".
Senior Brussels officials say the EU is struggling to come up with a coherent and effective response to the revelations of mass US and British surveillance of electronic communication in Europe, but that the disclosure that Merkel's mobile had been monitored was a decisive moment.
A draft report by a European parliament inquiry into the affair, being presented on Wednesday and obtained by the Guardian, says there has to be a discussion about the legality of the NSA's operations and also of the activities of European intelligence agencies.
The report drafted by Claude Moraes, the British Labour MEP heading the inquiry, says "we have received substantial evidence that the operations by intelligence services in the US, UK, France and Germany are in breach of international law and European law".
Rather than resorting to a European response, Berlin has been pursuing a bilateral pact with the Americans aimed at curbing NSA activities and insisting on a "no-spying pact" between allies.
The NYT reported that Susan Rice, Obama's national security adviser, had told Berlin that there would be not be a no-espionage agreement, although the Americans had pledged to desist from monitoring Merkel personally.
A high-ranking German official with knowledge of the talks with the White House told the Guardian there had been a "useful exchange of views", but confirmed a final agreement was far from being reached.
The Germans have received assurances that the chancellor's phone was not being monitored and that the US spy agency is not conducting industrial espionage.
However the official, who spoke on condition of anonymity because of the sensitivity of the talks, said German and US officials were still in the process of negotiating how any final agreement – the details of which could remain secret between both governments – would be formalised.
Their discussions, which include talks about so-called confidence building measures, are also bound-up with wider discussions with the EU regarding special privacy assurances that might be afforded to its citizens under a future arrangement.
"We want to be assured that not everything that is technically possible will be done," the German official added.
In Germany, the main government minister dealing with the NSA fallout, Hans-Peter Friedrich, has fallen victim to a reshuffle in the new coalition unveiled in Berlin at the weekend. Friedrich, from Bavaria's Christian Social Union, is not seen as an ally of Merkel's and was widely viewed to have performed less than robustly in the exchanges with the Americans.
His replacement as interior minister, by contrast, is a close ally of Merkel's – her former chief of staff and former defence minister, Thomas de Maiziere. Additionally, Merkel has brought a former senior intelligence official into the new coalition.
Alongside De Maiziere at the interior ministry, she has appointed Klaus-Dieter Fritsche, previously deputy head of the domestic intelligence service, Germany's equivalent of MI5.