Gap solitons near a band edge of a spatially periodic nonlinear PDE can be formally approximated by solutions of Coupled Mode Equations (CMEs). Here we study this approximation for the case of the 2D Periodic Nonlinear Schr{o}dinger / Gross-Pitaevskii Equation with a non-separable potential of finite contrast. We show that unlike in the case of separable potentials [T. Dohnal, D. Pelinovsky, and G. Schneider, J. Nonlin. Sci. {bf 19}, 95--131 (2009)] the CME derivation has to be carried out in Bloch rather than physical coordinates. Using the Lyapunov-Schmidt reduction we then give a rigorous justification of the CMEs as an asymptotic model for reversible non-degenerate gap solitons and even potentials and provide $H^s$ estimates for this approximation. The results are confirmed by numerical examples including some new families of CMEs and gap solitons absent for separable potentials.