i've noticed a few times, that a legendary enemy instantly gets his health back!

sometimes i had him under 50% and suddenly he was at full life again

i payed attention if this only happens when he mutates, but it has nothing to do with it...

Legendary's can "mutate" mid-fight, where they get a new trait and their health resets.

^^ Correct. Also I noticed in a battle with Kellogg, he stimmed himself up during the battle. You can hear the sound of him doing it.

They probably level up.

They do that every time for me. Unless i kill them in one shot

It's called a rage mechanic. Common in mmorpg boss fights, where if you don't kill an enemy at a certain point, the fight gets harder.

Some legendaries mutate quick, others take longer. Some don't at all.

every single legendary ive fought from normal to survival have always mutated at 50% health unless i was able to one shot it.