We investigate electrochemical properties of Mg in layered and spinel intercalation compounds from first-principles using TiS2 as a model system. Our calculations predict that MgxTiS2 in both the layered and spinel crystal structures exhibits sloping voltage profiles with steps at stoichiometric compositions due to Mg-vacancy ordering. Mg ions are predicted to occupy the octahedral sites in both layered and spinel TiS2 with diffusion mediated by hops between octahedral sites that pass through adjacent tetrahedral sites. Predicted migration barriers are substantially higher than typical Li-migration barriers in intercalation compounds. The migration barriers are shown to be very sensitive to lattice parameters of the host crystal structure. We also discuss the possible role of rehybriclization between the transition metal and the anion in affecting migration barriers.