There are several easy ways of defeating a Malamar, but one condition has to be set before anything can be done: do not let it set up too much, it's that point when things start looking bad.
Malamar has a x4 weakness to Bug types, so Pokemon like Scizor will easily scoop up the squid in ther pincers (pinsirs?).
Also, Malamar is probably the only Pokemon (bar it's pre-evolution) to have no resistances whatsoever. So hitting it with strong neutral moves is also a good means of defeating it.
Ghost-pokemon, mostly the ones that will get their job done faster than Malamar can Night Slash them, are a great choices as they prevent it from setting up with Superpower. Examples include Sableye, which can burn it and take next to nothing from Night Slash/Foul Play and Trevenant, which can take a Night Slash and retaliate with Will-O-Wisp.
These are but a few ways of dealing with Malamar, play out it's weaknesses, and it would not be as much of a nuisance as you think it is.
Source - Experience
Hope I helped!
