For many centuries, songe used to be the only word to mean "dream" in French. It cames from the Latin somnium which relates to somnus (sommeil, sleep).
Other romance languages have kept somnium as the main word for it (sp:sueño, it:sogno, pt:sonho, cat:somni, ro:somn...).
On the other hand, rêve was created from the verb resver that meant to wander, ramble or prowl. Resver etymology is not firmly established, there are competing theories.
Anyway, rêve had for a long time the negative connotation inherited from resver while songe was the neutral and positive word for dream.
Rêve lost its negative side and became more popular than songe in the nineteenth century.
Nowadays, the substantive songe is almost never used in casual French so un rêve and un songe are definitely not interchangeable unless a poetic/literary effect is expected.
The verb songer, while rare, is still used but has shifted its meaning from rêver to penser with a small nuance. Penser means to think (of something) while songer is more like to imagine the eventuality of something, to consider something. Compare:
Je pense me présenter aux élections. : Odds are high it will happen.
Je pense à me présenter aux élections. : I do not forget to do it.
Je songe à me présenter aux élections. : I'm still unsure and likely still weighing up the pros and cons.
We can see that in the songer case, there is still a part of dream in the sense imaginary images or events are showing up in your mind.
D’où vient le mot « rêver ? », Marc-Alain Descamps
Le mot, la chose, l'histoire, Daniel Fabre