Totes is a shortened form of totally, amplified with the common present-day slang suffix -s (compare, for instance, awks for awkward). It was documented on Urban Dictionary as early as 2003 and has probably been around considerably longer: totally itself was identified by F.Zappa and M.U.Zappa, (“Valley Girl”, 1982) as a core emphatic in Proto-Valspeak.
Totes magotes is an emphatic reduplicative form, comparable to easy-peasy or itty-bitty. Several sources attribute its first appearance, and perhaps its coinage, to the 2009 bromantic comedy I Love You, Man (but, again, it may have been around longer)†:
SYDNEY: You know what, we should jam together sometime, man.
PETER: Yeah! Totally! Totes magotes! Cool!
A comment on this very clip at YouTube clearly (and possibly ironically) demonstrates exactly the same formation processes at work on “crazily adorable”:
Totes McGotes, it's cray-cray adorbs. —TheAndrewj96
ADDED:
The suggestion by Damkerng T. and the source linked by fayalif, that the gotes piece represents G.O.A.T. = Greatest Of All Time is attractive and plausible. I suspect, however, that this is a retrospective folk etymology. Certainly most users betray no consciousness of this origin, spelling the syllable gote rather than goat.
ADDED, 10/23/14:
† And now Eric Duft's answer establishes that the phrase was in use as early as 2001.