I've spent quite a bit of time hunting down Morrissey and related records in the city, and it's a task that can often be unrewarding. Perversely, I usually find stuff when I'm not looking for it. I don't know if you live here or are visiting on holiday? If it's the latter, you probably don't have much time, in which case here are my recommendations:
1 - "Jussieu" on rue Linné in the 5eme is always worth a look-in. I once found a rare "Panic" promo 7-inch in there, and they have a very interesting and diverse stock anyway.
2 - "12 Inch" on rue de Palestro has a huge selection of, you guessed it, 12 inch singles. A ton of '80s stuff, and there's always some Smiths in there, often rarities. Highly recommended.
3 - "Boulinier" on Bd St-Michel in the 6eme is cavernous and dirt-cheap. I haven't been there in a while, but you could pick up a bargain. Hit-and-miss on quality, but definitely worth a try.
4 - "Troglodisc" on rue Fromentin in the 9eme. Again, big and cheap, but they have a lot of new wave, 80's and 90's stuff. I've been successful there in the past. Don't hang around here after dark though.
5 - The market at Clignancourt in the 18eme (near the Sacré-Cœur) is awash with 2nd hand vinyl stalls. Look out for a fat guy with a cigar and his peroxide-blonde wife (who bears a stunning resemblance to Debby Harry), their stall specialises in 80s rarities.
I hope that helps and good luck with your search. Word of warning about Monster Melodies though - much of their stock is vastly overpriced and the staff are notoriously unpleasant. If you suspect a record isn't worth what it's marked up as, it probably isn't.