Electron spin relaxation in paramagnetic Ga(Mn)As quantum wells is studied via the fully microscopic kinetic spin Bloch equation approach where all the scatterings, such as the electron-impurity, electron-phonon, electron-electron Coulomb, electron-hole Coulomb, electron-hole exchange (the Bir-Aronov-Pikus mechanism) and the s-d exchange scatterings, are explicitly included. The Elliott-Yafet mechanism is also incorporated. From this approach, we study the spin relaxation in both n-type and p-type Ga(Mn)As quantum wells. For n-type Ga(Mn)As quantum wells, where most Mn ions take the interstitial positions, we find that the spin relaxation is always dominated by the D'yakonov-Perel' (DP) mechanism in the metallic region. Interestingly, the Mn concentration dependence of the spin relaxation time is nonmonotonic and exhibits a peak. This is due to the fact that the momentum scattering and the inhomogeneous broadening have different density dependences in the nondegenerate and degenerate regimes. For p-type Ga(Mn)As quantum wells, we find that the Mn concentration dependence of the spin relaxation time is also nonmonotonic and shows a peak. The cause of this behavior is that the s-d exchange scattering (or the Bir-Aronov-Pikus) mechanism dominates the spin relaxation in the high Mn concentration regime at low (or high) temperature, whereas the DP mechanism determines the spin relaxation in the low Mn concentration regime. The Elliott-Yafet mechanism also contributes to the spin relaxation at intermediate temperatures. The spin relaxation time due to the DP mechanism increases with increasing Mn concentration due to motional narrowing, whereas those due to the spin-flip mechanisms decrease with it, which thus leads to the formation of the peak. The temperature, photoexcitation density, and magnetic field dependences of the spin relaxation time in p-type Ga(Mn)As quantum wells are investigated systematically with the underlying physics revealed. Our results are consistent with the recent experimental findings.