Criminal is an adjective and story is a noun. Why is "crime story" used instead of "criminal story"? While both crime and story are nouns. What's this latter combination?
Is "criminal story" even correct?
"Criminal" means "against the law", like "criminal behaviour", "criminal organisation", "criminal enterprise", and so on.
The story is not against the law, the story is about a crime, so it's a crime story, not a criminal story.
A crime story is a story about a crime.
A criminal story would be a story about a criminal.
Typically speaking, books written in this genre tend to be centered around the crime. They will sometimes get into the criminal's life, but they equally get into the lives of other characters, especially the crime solver.
If one were to write a book and label it as a "criminal story," it would be a story about a criminal, or criminals in general. It might cover life as a criminal, with all the trust challenges that come with that life. It may include crimes, but the individual crimes would be less important than the life of the criminal.
I am unaware of any story that sells itself as a "criminal story," but if one existed, that is what I would expect to see, as a native English speaker trying to make sense of a pair of words.
Crime story is a compound noun made of two base nouns. I think you were expecting an adjective-noun pair, but that's not how we express this idea in English.
Similar constructions from the linked source include "post office" and "fish tank".
"Criminal story" is not an immediately meaningful combination. We just don't use it that way, but sometimes we use similarly constructed phrases. A criminal trial is a trial about a crime, not a trial conducted in an illegal manner. Why can we say "criminal trial" and not "criminal story"? Unclear, but it may be because of the word "story". When naming genres, we seem to prefer compound nouns: "adventure story", "romance story", etc.
While writing a comment, I figured I should probably write it as an answer.
As brian_o said in his answer, crime story is a compound noun. Generally a compound noun is used to describe a more specific version of something. A post office is an office for post, a wood shed is a shed for wood, a crime story is a story about crime.
The main issue is that the word criminal has an adjective usage and a noun usage. So logically criminal story is just as correct as crime story. In usage, crime story is considered "correct" as it is the common usage.