Metasurfaces, and in particular those containing plasmonic-based metallic elements, constitute a particularly attractive set of materials. By means of modern nanolithographic fabrication techniques, flat, ultrathin optical elements may be constructed. However, in spite of their strong optical nonlinearities, plasmonic metasurfaces have so far been investigated mostly in the linear regime. Here we introduce full nonlinear phase control over plasmonic elements in metasurfaces. We show that for nonlinear interactions in a phase-gradient nonlinear metasurface a new anomalous nonlinear phase matching condition prevails, which is the nonlinear analog of the generalized Snell law demonstrated for linear metasurfaces. This phase matching condition is very different from the other known phase matching schemes. The subwavelength phase control of optical nonlinearities provides a foundation for the design of flat nonlinear optical elements based on metasurfaces. Our demonstrated flat nonlinear elements (i.e. lenses) act as generators and manipulators of the frequency-converted signal.