We report the discovery of a metamagnetic phase transition in a polar antiferromagnet Ni$_3$TeO$_6$ that occurs at 52 T. The new phase transition accompanies a colossal magnetoelectric effect, with a magnetic-field-induced polarization change of 0.3 $mu$C/cm$^2$, a value that is 4 times larger than for the spin-flop transition at 9 T in the same material, and also comparable to the largest magnetically-induced polarization changes observed to date. Via density-functional calculations we construct a full microscopic model that describes the data. We model the spin structures in all fields and clarify the physics behind the 52 T transition. The high-field transition involves a competition between multiple different exchange interactions which drives the polarization change through the exchange-striction mechanism. The resultant spin structure is rather counter-intuitive and complex, thus providing new insights on design principles for materials with strong magnetoelectric coupling.