What you are seeing here is apparently a corner case on the journey of a verb + preposition to a prefixed verb.
Ich lege ein Kissen unter deinen Kopf.
is the verb legen plus the preposition unter. All fine, no problem.
Ich unterlege deinen Kopf mit einem Kissen.
doesn’t work separated, as in
Ich lege deinen Kopf mit einem Kissen unter.
(at least not in my world), while
Ich lege deinem Kopf ein Kissen unter.
works very well.
In perfect, they look like this:
Ich habe deinen Kopf mit einem Kissen unterlegt
Ich habe deinem Kopf ein Kissen untergelegt
Both seem to work.
So, apparently, there seems to be a difference between transitive and intransitive usage of unterlegen – the transitive usage uses the verb in separable form, while intransitive usage takes the inseparable form.
There is quite a number of verbs that are both separable and inseparable and have a different meaning in both cases like umfahren (e.g., “Ich umfahre den Fussgänger” vs. “Ich fahre den Fussgänger um”), but unterlegen is the first one where I realize that separability might depend on transitive/non-transitive usage.
Looking at my answer after some time, I might have chosen a better example: unterlegen may be used with cushions and heads (and works), but is mostly used as a “technical” action to adjust something in height, like in:
Der Schrank wackelt, da müssen wir wohl was unterlegen
Der Bolzen ist zu lang. Ich unterlege da wohl eine Scheibe.