We develop a relativistic Coulomb-corrected strong field approximation (SFA) for the investigation of spin effects at above-threshold ionization in relativistically strong laser fields with highly charged hydrogen-like ions. The Coulomb-corrected SFA is based on the relativistic eikonal-Volkov wave function describing the ionized electron laser-driven continuum dynamics disturbed by the Coulomb field of the ionic core. The SFA in different partitions of the total Hamiltonian is considered. The formalism is applied for direct ionization of a hydrogen-like system in a strong linearly polarized laser field. The differential and total ionization rates are calculated analytically. The relativistic analogue of the Perelomov-Popov-Terentev ionization rate is retrieved within the SFA technique. The physical relevance of the SFA in different partitions is discussed.