En parlant du diable...
Further to Twin Star's comments, the all-encompassing view from Montparnasse is probably the best, but, really, the Eiffel Tower while cliched is a far better experience.
Prepare for disappointment with Les Catacombes, despite it being top of my list when I came as a tourist in 2003 I still have not gotten around to going in two years as a resident. Two weekends ago my sister-in-law was over so we decided to go only to discover they were closed for a technical reason. It seems they have been having some issues with the ventilation since October and it is very hit and miss as to whether they are open - unfortunately the website is not very useful either so you run a risk of missing it I'm afraid. Hopefully not though!
Absolutely make time for Pere Lachaise, which is the finest cemetery in the city. However, there are also ones at Montparnasse (Serge Gainsbourg, JP Sartre, Samuel Beckett), one at Montmartre - near the Moulin Rouge - (Nijinsky, Truffaut, Stendahl, Zola [although his bones have been moved]) and Passy [near Trocadero] (Manet, Faure). I love the cemeteries, and oftentimes it is not the famous ones whose graves are the most elaborate. I love taking a walk and spotting a name on a tomb and then Googling them when I get in to find out their story.
EDIT: Oh, and Victor Noir was not sealed off last time I went so if you want to rub his bronze bit feel free!
Saint Chapelle on the Ile de Cite has a 'Crown of Thorns' relic.
Le Manoir de Paris is a kind of London Dungeons type walk through experience. It looks
very scary though so I have never been.
http://lemanoirdeparis.fr/accueil/
Musee Grevin on Boulevard Haussmann reputedly has the actual bathtub and knife from the murder of Marat. It is very pricey for a wax museum though so haven't been there yet either!
http://www.grevin.com
There is a ghost walk tour but I think ot does not start up again until April.
http://www.mysteriesofparis.com
The Porte Dorée station was witness to a real-life "closed room" murder mystery in the 30s, remains unsolved but most likely assassainated by
La Cagoule.
The Museum of Natural History at the Jardin des Plantes is great for old bones and oddities.
http://www.mnhn.fr/le-museum/
The Musuem of Medecine has some creepy weird stuff in cabinets but I think it is a by appointment only place.
http://www.univ-paris5.fr/CULTURE/Musee ... a-Medecine
To be honest, from a Fortean point of view, modern Paris is not as mysterious as you would hope. For all the revolution, drama and bloodshed that the streets have seen there are few ghost tales.
However, it is an amazing city and one which you will not possibly be able to even scratch the surface of in a weekend. In two years I am still far from discovering a percentage of what there is to offer.
If you want any bar/restaurant info or have more specific areas/subjects you'd like more info on give me a shout!