1. Ask them if they think MLG Halo is a first person shooter. MLG's setting for Halo removes about the same amount of gameplay elements from default as Melee players do from Melee. In fact, for Halo 3 and Reach, CUSTOM MADE maps were used for competitive play. Not only did they systematically alter weapon spawn times and locations, but maps were built from the ground up. Even with all of these setting adjustments, no one would ever watch an MLG Halo event and think "this isn't a first person shooter." The same holds true for Melee.
2. If Smash 4 was released as an exact copy of Melee but with our current rules set as the default, would it not be a fighting game? Of course it would be. If that version of Smash 4 would be considered a fighting game, then why not Melee with those same exact settings?
3. How many rules can you change before your game becomes illegitimate for competition? If the next SF had a 500 second timer by default and the community agreed to change it to 99 seconds, is that SF game no longer a fighter? What if the next MvC was an amazingly balanced game, but they included X-factor powerups that spawned randomly. These powerups do not have to be forcibly removed from the game in any obscure way, they are simply turned off in the basic options menu. Would the FGC really abandon such a well-suited game just because the developers included a casual-oriented feature as default with a competitive-oriented rule set optional? I'm sure if I knew enough about fighting games, I could already point to an example of the FGC preemptively banning a stage or glitch or tactic simply because it didn't fit with their vision of how that game should be played.
If they simply disagree that even default Melee is a fighting game, then:
4. Genres are 90% opinion-based. They are a way of grouping like things. In music, we observe different styles of sound, instruments used, types of melodies and harmonies and all that good stuff. The ones with similar traits are grouped together. These days, it's probably impossible to create a song that won't have traits from multiple genres. As far as the fighting game genre is concerned, there are a few main similarities between each game, and many games take interesting twists in these similarities.
Melee has so many similarities to other fighters, both basic and complex, that to consider anything but a fighter is ridiculous. There are two opponents whose goal it is to defeat the other by ringout. Melee doesn't have the same sort of health system as most fighters, but it does have percentage-based damage that serves a similar purpose of getting your opponent closer to death. Ringouts are in many traditional fighters, and while I'm not sure any have a system for recovering back to the stage after one, it is no doubt a ringout-like concept. Again, if a SF game were released with the ability to double jump back to the stage, would it suddenly not be a fighter? Unlikely. These are all fairly basic similarities though, so how can we be sure I'm not just cherry-picking obscure topics like "health" to twist Melee into the fighting genre? You can be sure because of how many elements are taken distinctly and directly from traditional fighters. Combos are an obvious one. Training Mode has a counter the keeps track of how many successive hits you can land without the opponent being able to escape. My favorite similarity (and one that is often overlooked) is the RPS element of Attack-Block-Grab. In most traditional fighters, blocks are a tool used solely to block attacks. In order to prevent blocks from being abused, the developers include grabs, which are a different type of attack that beats blocking. Grabs will make quick work of anyone that tries to abuse their ability to block all other attacks, but in order to balance grabs into the equation, they must obviously make it so attacks beat grabs. This is the exact system Melee uses. If you spam attacks, they will get shielded. If you spam shield, you get grabbed. And if you spam grabs, you will get kicked in the jaw. This is such a core element of so many traditional fighters that it is very clearly not an accident or coincidence.
Take your pick. I can rattle off arguments all day that destroy anything a Capcom fanboy can come up with against Melee being 1. a legitimate competitive game and 2. a fighting game. They simply have no ground to stand on because all of the facts are on our side. If Melee were built with the usual SF or MvC characters, you can be sure it would have quickly been accepted as a competitive spinoff of traditional fighters. That is one last thing to keep in mind when arguing this stuff is that Melee is NOT a traditional fighter. There are always subgenres that you can group things in, and this holds true for all games. Fighters with multiple characters and tagouts are not traditional in any sense, so be sure you accept that Melee is not traditional either before arguing that it's still a fighter. Personally, I use the term platform-fighter because I think the main aspect that separates Melee from other fighters is its movement, which is essentially platforming.