Malin is an interesting word as it started to be negative only (qui fait [du/le/∅] mal, "doing evil") but evolved to a shifted alternate positive meaning ("being astute, smart").
As in you question, it is also often used in antiphrasis, so both of these sentences are negatives, although with a slight difference:
Il a l'air malin.
Il n'a pas l'air malin.
In the first case, the person has just done something or is affected by something that just happen, and is looking stupid. This is a temporary state.
In the second one, the person just doesn't look smart. This is more of a permanent state. If you are familiar with Spanish, that's a typical use case of estar/ser difference.
Depending on the context, il a l'air malin might also be used a positive way (he looks smart).
Note also that malin has two feminines, maligne and maline. The second one is prevailing nowadays, especially when "smart" is the expected meaning.
Finally, you migh read either of these three sentences:
Elle a l'air maligne. (old fashioned)
Elle a l'air maline. (usual)
Elle a l'air malin.
In both first case, mali(g)ne applies to elle (elle a l'air d'être maline, "she looks smart/stupid*)
In the last one, malin applis to air (look), which is a masculine word ("she has a smart/stupid look").