What exactly is the criterion for unlocking the NG+? I've completed one of the "ends the game" levels on normal difficulty, but the option doesn't appear. Do I need to complete all endings, or complete the ending on extreme difficulty, or both, or something else? Or is there some sort of bug?

"The Way Out" doesn't unlock NG+. You have to complete the "true" ending in order to access it. As long as you finish the final level, even on Casual, you can get to NG+.

EDIT: To be more specific, there are five separate endings. One side ending for "The Way Out," one bad ending for when the final level is failed due to Azra's death, and three good endings for passing the final level. Which of those three good endings you get depends on whether your ally for that level is unhurt, hurt but not dead, or dead. Only the three good endings will unlock NG+. The side-ending and failure ending won't.

Thanks.

I somewhat object to the "run away" ending not being treated as a proper ending. It even says "ends the game" as the level "reward", when in reality there is no reward for completing it whatsoever (beyond the usual scrap and XP). It also goes into end credits and drops you back to the title screen, so it's a bit weird that it somehow "doesn't count". If the game is going to let you make plot decisions, it could at least make them matter.

However, at least that's clear.