Considering the viscoelastic memory effect, we study the correlated motion of two hydrodynamically coupled colloidal particles, each of which confined in a harmonic potential well, in a Kelvin-type and Maxwell-type viscoelastic medium. We find that viscoelastic relaxation plays a significant role in modifying the correlation, particularly the cross correlation. We also find that both the real and imaginary parts of the response function are significantly different from the viscous medium case. In particular there is a phase shift between the vanishing imaginary part and the maximal real part of the response function in a viscoelastic medium. In addition imaginary part of the cross correlation response function exhibits a net energy loss (gain) behavior when the elasticity parameter of the medium is larger (smaller) than the critical value for Kelvin (Maxwell) viscoelastic fluid. Some implication of our results and their connection with previous works are discussed.