High harmonic generation modulated by a weakly perturbing laser field enables new wave mixing frequency components, thus allowing in-situ spatiotemporal measurements and wavefront control of attosecond optical pulses. However, perturbative high harmonic wave mixing from plasma surfaces has not been investigated extensively. In this study, we theoretically analyze the plasma high harmonic generation process in the relativistic regime modulated by a perturbing laser field with an arbitrary frequency. New wave mixing frequency components satisfying the conservation laws of photon energy and momentum are observed. The wave mixing component intensities adhere to a power law for the perturbating laser photon number as the perturbing laser intensity increases, thereby revealing perturbative behaviors in the nonperturbative, extremely nonlinear optical process of high harmonic generation. Detailed studies reveal the polarization selection rule and physical mechanism of high harmonic wave mixing. The modulation of the relativistic factor or mass enhancement of electrons on the plasma surface by the perturbing laser field is believed to result in high harmonic wave mixing in the relativistic regime.