The performance of the high-baud-rate and high-order-modulation-format short-reach coherent transmission systems is sensitive to the in-phase and quadrature (IQ) skew. The conventional receiver IQ skew compensation schemes based on adaptive equalizers (AEQs) suffer from the IQ skew enhanced timing jitter incurred by the clock recovery algorithm (CRA), resulting in a serious sensitivity degradation. In this paper, we first propose a novel multiplication-free timing phase error detector (TPED) with the gain insensitive to the receiver IQ skew and the capability to deal with the complex-valued Nyquist signal with an arbitrary roll-off factor and its real-valued IQ tributaries. Based on the TPED, we then propose a new all-digital feedback CRA able to compensate for the receiver IQ skew. With the novel CRA, the IQ skew enhanced timing jitter is eliminated and the receiver sensitivity can be improved by more than 1 dB for the 61 GBaud dual-polarization Nyquist 16QAM system for an IQ skew of 5 ps. Furthermore, the proposed CRA can reduce the computation complexity of the AEQ by more than 25% compared with the existing schemes by relieving the AEQ from IQ skew compensation. Both numerical simulations and experiments are carried out to validate the advantages of the proposed algorithms. The high-skew-tolerant and low-complexity CRA is a strong candidate for the power-sensitive high-speed short-reach coherent transmission systems.