We present an analysis of the electro-osmotic flow of electrolytic solutions in a microchannel with patterned hydrodynamic slippage on channel walls. A set of governing equations is formulated to account for the effects of small variations in hydrodynamic slippage over the microchannel walls on the electro-osmotic flow. These equations are then solved analytically by using the perturbation method. Two frequently encountered surface patterns, (i) cosine wave variation and (ii) square wave variation in slip length, are considered in our analyses. The results show that patterned slippage over microchannel walls can induce complex flow patterns (such as vortical flows) in otherwise plug-like electro-osmotic flows, which suggests potential applications of such flows in microfluidic mixers.