The Competition and Markets Authority (CMA) expressed "serious concerns" to the European Commission about the deal.
It warned the merger could cause "long-term damage" for UK consumers as it would leave only three mobile networks.
CK Hutchison, the owner of Three, said it was "very disappointed" the CMA had published the letter.
The European Commission has until 19 May to make a decision on Three's proposed £10.5bn takeover of O2.
Hutchison said: "It is no surprise that CMA opposes the merger. It always has, and so has Ofcom. But it is for the Commission to assess any competition concerns, on the basis of the facts and proposed remedies."
Sky, Virgin, Tesco and UK Broadband have agreed to use Three-O2's share of UK airwaves to offer their own mobile packages, the company said.
"The entry of so many diverse, strong and committed players will ensure that there is plenty of competition in the UK market and plenty of counter offers to any supposed price increases post-merger," it said.
Three's owner added that it would invest £5bn in UK mobile infrastructure and that new entrants would add a further £5bn.
The planned purchase of O2 by Hutchison, which is owned by Asia's richest person Li Ka-shing, was announced early last year.
If approved, the deal would leave just two other major UK operators: EE and Vodafone.
Hutchison sent its suggested remedies to the European Commission last week to smooth the takeover.
The CMA said the remedies "fall well short" and insisted the Commission should instead force most of O2 or Three's mobile network to be sold off after the deal.
"Absent such structural remedies, the only option available to the Commission is prohibition," Alex Chisholm, chief executive of the CMA, said in the letter to the European Commission.
European competition commissioner Margrethe Vestager will make the final decision on the deal, rather than UK regulators.
"At best we see UK deal approval odds at 50/50. The risk, here, is the decision could become increasingly political (from a UK perspective it already is) as it's so close to the Brexit vote," said Mandeep Singh, a partner at Redburn analysts.
Campaigners for a British exit from the EU - known as "Brexit" - have already raised concerns about the European Commission having the final say instead of the CMA or Ofcom.
The Commission has previously approved deals in Ireland, Austria and Germany that reduced the number of mobile networks from four to three.
The UK telecoms market is going through significant change, with broadband, mobile and subscription TV providers increasingly competing with each other.
BT re-entered the mobile market earlier this year after its £12.5bn takeover of EE was approved by the CMA.
Tom Mockridge, Virgin Media chief executive, said: "A combined O2-Three would provide a counter balance to the strength of BT/EE, offering an alternative source of capacity to other providers who will drive competition in their own right."
The planned merger of mobile networks O2 and Three should be blocked or severely restricted by EU regulators, the UK competition watchdog has said.