The Gothic genre is known for a few common themes. One is an element of the supernatural, some unexplained influence or phenomenon. This is definitely present in the story, as the narrator is spooked by the second cat's strange likeness to his dead cat Pluto. He says:
"I am almost ashamed to own that the terror and horror with which the animal inspired me, had been heightened by one of the merest chimæras it would be possible to conceive."
The supernatural element here is not only that it seems that Pluto is back from beyond the grave to haunt the narrator, but that he has returned with a tiny patch of white fur in the shape of a gallows.
Another common theme in Gothic literature is the evil side of the human nature and the emergence of insanity. This is absolutely the case for the narrator, who, he claims, has always been kind, gentle, and an true animal-lover. After he took to alcohol, however, he was abusive to both his many pets and his wife, eventually killing both his favorite animal and his wife. The narrator claims that some of this perverseness, as he calls it, lives in all of us, saying:
"[...] perverseness is one of the primitive impulses of the human heart -- one of the indivisible primary faculties, or sentiments, which give direction to the character of Man. Who has not, a hundred times, found himself committing a vile or a silly action, for no other reason than because he knows he should not?"
In this story, we are all capable of such violence, deep down.
As for his decent into insanity, it is indeed hard to read the story without the mental confusion and angst of the narrator to be clearly shown. Certain lines like the following demonstrate this:
" And now was I indeed wretched beyond the wretchedness of mere Humanity. And a brute beast -- whose fellow I had contemptuously destroyed -- a brute beast to work out for me -- for me a man, fashioned in the image of the High God -- so much of insufferable wo! Alas!"
To get so worked up because you think your pet cat is haunting you from beyond the grave is definitely a red flag and shows that the narrator is suffering a severe break with reality. All of these features of the story place it clearly in the Gothic genre.