[hdctambien]

I never thought about this until now, but I think this is a case of an interfix. So, it is turning "another" in to "a-whole-nother" much like "abso-f*ing-lutely" or "legend-and-I-hope-you're-not-lactose-intolerant-because-the-second-half-of-that-word-is-DAIRY!"

[hythloday]

Technically it's not an interfix (interfices don't have a semantic meaning) but a tmesis.