It has recently been proposed that the inertial interval in magnetohydrodynamic (MHD) turbulence is terminated at small scales not by a Kolmogorov-like dissipation region, but rather by a new sub-inertial interval mediated by tearing instability. However, many astrophysical plasmas are nearly collisionless so the MHD approximation is not applicable to turbulence at small scales. In this paper, we propose an extension of the theory of reconnection-mediated turbulence to plasmas which are so weakly collisional that the reconnection occurring in the turbulent eddies is caused by electron inertia rather than by resistivity. We find that the transition scale to reconnection-mediated turbulence depends on the plasma beta and on the assumptions of the plasma turbulence model. However, in all of the cases analyzed, the energy spectra in the reconnection-mediated interval range from to .