Tmesis is also used to describe this construction, when a lexical word is inserted as an intensifier. And yes, expletives are very often used as intensifiers in these cases.
It's also originally found in words like whatsoever/what-so-ever, howsoever/how-so-ever, etc., which are now words in their own right.
There are rules about where we stick the intensifier, based on prosody in English. We don't find *unbe-fucking-lievable but we do find abso-fucking-lutely. An interesting thing about a-whole-nother is where another is divided; it's not *an-whole-other as one would expect.