Detect that given element has been removed from the DOM without sacrificing performance

As you said, MutationObserver only allows you to detect when the children of an element are manipulated. That means you'll need to listen to the parent and check what changes were made to see if the target element was removed.

function onRemove(element, callback) {
  const parent = element.parentNode;
  if (!parent) throw new Error("The node must already be attached");

  const obs = new MutationObserver(mutations => {
    for (const mutation of mutations) {
      for (const el of mutation.removedNodes) {
        if (el === element) {
          obs.disconnect();
          callback();
        }
      }
    }
  });
  obs.observe(parent, {
    childList: true,
  });
}

then with your example instead of

element.onRemove(() => releaseKraken(element));

you can do

onRemove(element, () => releaseKraken(element));

This approach should be plenty fast if all you are doing is watching a single element. While it may seem like a decent amount of looping, it is pretty rare for removedNodes to be more than one node, and unless something is removing tons of siblings all at once, mutations is going to be quite small too.

You could also consider doing

callback(el);

which would allow you to do

onRemove(element, releaseKraken);

An alternative, shorter version of loganfsmyth's excellent solution:

function onRemove(el, callback) {
  new MutationObserver((mutations, observer) => {
    if(!document.body.contains(el)) {
      observer.disconnect();
      callback();
    }
  }).observe(document.body, { childList: true });
}

Usage is the same:

onRemove(myElement, function() {
  console.log("The element was removed!");
})