The formalism of quantum electrodynamics for treating the interelectronic-interaction correction of first order in 1/Z to the two-electron part of the nuclear recoil effect on binding energies in atoms and ions is developed. The nonperturbative (in αZ) calculations of the corresponding contribution to the energies of the 1s2 state in He-like and the 1s22s and 1s22p1/2 states in Li-like ions are performed in the range Z=5-100. The behavior of the two-electron part of the nuclear recoil effect beyond the lowest-order relativistic approximation as a function of Z is studied.