Ensuring the operational reliability of wind turbines, particularly in cold climates, hinges on the effective detection of blade icing. Rapid and accurate identification of icing events is crucial for optimized turbine operation, enabling timely activation of de-icing systems and, when necessary, turbine shutdown, thereby protecting structural integrity. This paper introduces a novel supervised deep learning architecture, the Multi-scale Wavelet Graph Convolutional Network (MWGCN), explicitly designed for blade icing detection. Initially, the MWGCN utilizes wavelet decomposition to break down multivariate signals into their fundamental time-frequency components. Subsequently, a temporal graph convolutional network is employed to model the inter-variable relationships within these multi-scale wavelets, along with their temporal evolution. Furthermore, this work pioneers the incorporation of scale attention within the MWGCN to boost performance and proposes a method to address class imbalance in training datasets. Comprehensive experimental evaluations demonstrate the superior effectiveness of the proposed MWGCN in blade icing detection, surpassing eight state-of-the-art algorithms. Notably, the MWGCN achieves F1-scores that are 17.2 and 11.3% higher than the most competitive existing models on benchmark datasets.