I don't think anyone is saying that EVERYTHING is always based on some mechanics at all times, or that things much be based on 'checks' necessarily. It is entirely dependent on the game, the participants, etc. Again though, principles, applied through some sort of process to carry out some agenda, is at the core of it. I would say it is never BAD to articulate those.
So, for instance, if I was running a Dungeon World game and the idea of solving a mystery came up, I have some things I can fall back on, right? Like I know that we're 'playing to see what happens', and we have a general principle of 'fiction first' and the GM 'pushes' things. There is usually not a lot of established story or 'myth' either, although perhaps a GM would be wise to have devised some ideas about who killed Miss Green, where and with which weapon (these ideas should probably be highly provisional though).
So, this type of game will proceed through the GM looking at what the players are aiming for, and feeding them interesting obstacles in each scene. Success and failure will basically determine how hot/cold they get in terms of a solution, and details can be drawn from the GM's 'map' of the situation. In some cases a player might effectively dictate something (you can kind of do this with judicious use of Spout Lore) or maybe the GM goes and asks a player to supply some fact or other (this is a good reaction to say looking for a clue in a new location).
Now, DW is certainly not a murder mystery game, and I'm sure other rules sets do it better, but this is certainly a case where the principles of the game won't really work against you in any case of creating a narrative. I think this brings up a point about narrative focus games, their concepts are pretty universal, because they are mostly 'meta-game', and thus don't depend much on a specific fictional context. This is opposed to D&D and other classic games that focus on "mechanics as rules of the world" and mostly ignore the table. D&D's best bet for romance or mystery is to just not pay attention to its rules at all! Most of DW will at least help you, somewhat.