We consider the problem of spatial channel covariance matrix (CCM) estimation for intelligent reflecting surface (IRS)-assisted millimeter wave (mmWave) communication systems. Spatial CCM is essential for two-timescale beamforming in IRS-assisted systems; however, estimating the spatial CCM is challenging due to the passive nature of reflecting elements and the large size of the CCM resulting from massive reflecting elements of the IRS. In this paper, we propose a CCM estimation method by exploiting the low-rankness as well as the positive semi-definite (PSD) 3-level Toeplitz structure of the CCM. Estimation of the CCM is formulated as a semidefinite programming (SDP) problem and an alternating direction method of multipliers (ADMM) algorithm is developed. Our analysis shows that the proposed method is theoretically guaranteed to attain a reliable CCM estimate with a sample complexity much smaller than the dimension of the CCM. Thus the proposed method can help achieve a significant training overhead reduction. Simulation results are presented to illustrate the effectiveness of our proposed method and the performance of two-timescale beamforming scheme based on the estimated CCM.