When relying on Newton iterations to solve nonlinear problems in the context of Reduced Basis (RB) methods, the assembling of the RB arrays during the online stage depends on the dimension of the underlying high-fidelity approximation. This is more of an issue 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 combined to evaluate both the residual vector and the Jacobian matrix very efficiently in the case of complex parametrized nonlinear mechanical problems. We compare this strategy with the classical DEIM approach and we derive a posteriori error estimates on the solution accounting for the contribution of DEIM/MDEIM errors. The effectiveness of the proposed framework is assessed on quasi-static nonlinear problems. In particular, we consider a nonlinear elasticity problem defined on a cube and a mechanical model describing heart contraction, for an idealized left ventricle geometry. The latter is a coupled problem, in which the activation of the heart contraction is given by the solution of an electrophysiology model. Our numerical results show that MDEIM is preferable to the classical DEIM, both in terms of efficiency and accuracy. (C) 2017 Elsevier B.V. All rights reserved.