The newspaper, quoting unidentified lawyers close to the talks, said the settlement negotiations between the Justice Department and the Internet titans were at an early stage.
It said it was still unclear whether the talks would resolve antitrust objections to the agreement or result in a deal acceptable to the two California-based firms.
The newspaper said the companies were discussing concessions in the settlement talks with the government over the deal which would put Google technology to work targeting search ads on Yahoo pages.
"These include capping the volume of Google ads Yahoo would use, assurances that Yahoo would continue to compete in search ads, and a reporting mechanism to ensure compliance," the Wall Street Journal said.
Software giant Microsoft, advertisers and regulators have raised objections to the planned online advertising tie-up between Google and Yahoo, respectively number one and number two in the Internet ad market.
They claim it would allow Google to tighten its grip on online advertising and restrict competition.
Industry analysts have warned that politicians and regulators blamed for letting financial markets self-destruct may use the Google-Yahoo tie-up to show they are better watching out now for the publics economic interests.
Microsoft senior vice president and general counsel Brad Smith has argued the deal would give Google "an unprecedented level of control over advertising for search on the Internet -- up to 90 percent potentially of all search ads."
Microsoft is number three in the online ad market and made a failed bid earlier this year to take over Yahoo, which expects hundreds of millions of dollars in revenue from the ad tie-up with Google in the first year alone.
Google and Yahoo announced on Oct. 3 that they were delaying the start of the alliance until at least Oct. 22 to give regulators more time to look at it.