We consider the problem of designing sequences with good auto- and cross-correlation properties for multiple-input multiple-output (MIMO) radar systems. This design problem aims to minimize a polynomial function of the transmit waveforms. The problem becomes more challenging in the presence of practical constraints on the waveform such as the constant modulus constraint (CMC). The aforementioned challenge has been addressed in the literature by approximating the cost function and/or constraints, i.e. the CMC. In this work, we develop a new algorithm that deals with the exact non-convex cost function and CMC. In particular, we develop a new update method (Correlation-Gradient-Descent (CGD)) that employs the exact gradient of the cost function to design such sequences with guarantees of monotonic cost function decrease and convergence. Our method further enables descent directly over the CMC by invoking principles of optimization over manifolds. Experimentally, CGD is evaluated against state-of-the-art methods for designing uni-modular sequences with good correlation properties. Results reveal that CGD can outperform these methods while being computationally less expensive.