This is an Arthurian murder mystery. It's set in the time just before Arthur becomes high king, which in Hays's conception is after he's been battling Saxons for quite some time; he's trying to get elected by the other kings, not divinely chosen. If you believe there might have been an historical Arthur, this might be an historical mystery. Certainly the magic Merlin uses is easily recognizable to modern eyes as science, and seems meant to be so.
As I said in another context a few days ago, I had a rabidly Arthurian phase when I was a teenager. I read the whole gamut from determinedly greasy-haired historical anti-romanticism to willfully rosy-eyed flights of legend. The Killing Way is definitely towards the former end of the spectrum. The battles Arthur fights are not romanticized, and particularly their aftermath is not romanticized: Malgwyn, the narrator, has lost a wife and an arm to the Saxons and is not, at the beginning of the book, particularly sure he thanks Arthur for saving him.
What I'm saying here, I guess, boils down to, "If you like this kind of thing, this'll be the kind of thing you like." It's solid but not particularly exciting. It doesn't make the mistake too many Arthurian novels do, of attempting to fit in all the author's favorite bits of legend at once. This may be because it's structured in a way that looks to allow the author as many sequels as he feels like writing--it reads very similarly to the opening of other long mystery series I've liked. I'd say that if you would like Rosemary Sutcliff plus Ellis Peters, maybe give this one a go.