Gothic or Horror Fiction; Mystery; Psychological Thriller and Suspense
For a story in which nothing much happens, Poe really threw a lot of genres into the pot. Let's check out how they all work together:
Gothic
Okay, this isn't a traditional gothic story, and it's not particularly scary. Most of the excitement happens off camera, behind the scenes, out of the narrator's realm of vision.
But it is super creepy that G— and his men skulk through the shadows every night, using implements like "fine long needles" and "microscopes." They not only sneak into D—'s house, but they also toss over the two neighboring houses, presumably those of perfectly innocent Parisian citizens.
Creepy authority figures? Total lack of privacy? The feeling that your belongings are constantly being rifled? Straight Gothic, baby.
Psychological Thriller and Suspense
Sure, nobody jumps off of buildings or airplanes, but still you've got spying, murder, and possibly adultery. It ain't James Bond, but there's plenty of heart-stopping (well, okay, not really heart-stopping) suspense.
And the most thrilling part is listening to Dupin detail his game of wits with D—. This is a battle of the brains, not to mention that the poor royal lady is no doubt under some intense psychological stress. And the ending just ramps up the thrills, when we get the eleventh-hour revelation that Dupin is engaged in a long-standing feud with D—.
Mystery
But what the feud is, or what the letter says, or what political events are stemming from it—that is all a mystery. Mystery drives the adventure, creates the creepy Gothic mood, fuels the psychological mind games, and provides the suspense.
The story pretends, so to speak, that the only mystery is: "How does Dupin manage to do in two days, what G— and his force couldn't do in over ninety?" Dupin spends a big chunk of the story explaining this to the narrator. But that's kind of a coy move on Poe's part, because obviously the mystery is totally different: the real mystery is all the content that just might be right under our noses—or might not actually matter at all. You never know with Poe.