Magnetorheological elastomers (MREs) are soft solids that can undergo large and reversible deformation in the presence of an externally applied magnetic field. This coupled magneto-mechanical response can be used for active control of surface roughness and actuation in engineering applications by exploiting the reversible instabilities in these materials. In this work, we develop a general mathematical formulation to analyse the surface instabilities of a finitely deformed and magnetised MRE half-space and find the critical stretch that causes bifurcation of the solution of the resulting partial differential equations. The equations are derived using a variational approach in the reference configuration and the null-space relating the incremental solutions is presented to provide a basis for post-bifurcation analysis. Details of the numerical calculations are presented to clearly identify and discount non-physical solutions. Stability phase diagrams are presented to analyse the effect of material parameters and strength/direction of magnetic field.