When using Newton iterations to solve nonlinear parametrized PDEs in the context of Reduced Basis (RB)methods, the assembling of the RB arrays in the online stage depends in principle on the high-fidelityapproximation. This task is even more challenging when dealing with fully nonlinear problems, for which the global Jacobian matrix has to be entirely reassembled at each Newton step. In this paper the Discrete Empirical Interpolation Method (DEIM) and its matrix version MDEIM are exploited to perform system approximation at a purely algebraic level, in order to evaluate both the residual vector and the Jacobian matrix very efficiently. We compare different ways to combine solution-space reduction and system ap-proximation, and we derive a posteriori error estimates on the solution accounting for the contribution of DEIM/MDEIM errors. The capability of the proposed approach to generate accurate and efficient reduced-order models is demonstrated on the solution of two nonlinear elasticity problems.