Has anyone heard of or played the PS3 video-game Folklore? That's an example of this, and a very good one at it. Also the TV show Pushing Daisies seems to cross these two genres. If anyone knows of a novel like these, let me know, I need to read it!
Any Discworld novel with "Sam Vimes" in the blurb (though I only recall The Fifth Elephant and Thud! having murder investigations.) I wonder sometimes why Pratchett made a world full of witches, wizards and dragons... and chooses to make a series out of the police force, but I think it's enjoyable nonetheless.
The brilliant thing about the Sam Vimes stories is they're good old police stories but because of the preset fantasy world, Pratchett can drop in characters and side plots that would be ridiculous or incredibly hard to work into a normal police story. Just to take Thud! as an example - you'd never see Columbo or anyone from Prime Suspect having to spend the day sorting out a murder in a species they know little about, then go home to a wife who keeps dragons - those details don't add much to the basic plot but they make the story. With the same story in mind, few police dramas have a police officer having to worry about when the last time she tasted blood was, just in case in gets in the way of her duties, or another having to find clothes in the middle of an investigation, because she just turned back from being a werewolf. I think focusing on the most ordinary element of a fantasy story makes it all the richer, purely because you're making the fantastical the background which makes the 'plain' (none of Pratchett's characters are plain though) all the more enjoyable.
