Red novae are optical transients erupting at luminosities typically higher than those of classical novae. Their outbursts are believed to be caused by stellar mergers. We present millimeter/submillimeter-wave observations with ALMA and SMA of the three best known Galactic red novae, V4332 Sgr, V1309 Sco, and V838 Mon. The observations were taken 22, 8, and 14 yr after their respective eruptions and reveal the presence of molecular gas at excitation temperatures of 35-200 K. The gas displays molecular emission in rotational transitions with very broad lines (full width $sim$400 kms). We found emission of CO, SiO, SO, SO$_2$ (in all three red novae), H$_2$S (covered only in V838 Mon) and AlO (present in V4332 Sgr and V1309 Sco). No anomalies were found in the isotopic composition of the molecular material and the chemical (molecular) compositions of the three red novae appear similar to those of oxygen-rich envelopes of classical evolved stars (RSGs, AGBs, post-AGBs). The minimum masses of the molecular material that most likely was dispersed in the red-nova eruptions are 0.1, 0.01, and 10$^{-4}$ M$_{odot}$ for V838 Mon, V4332 Sgr, and V1309 Sco, respectively. The molecular outflows in V4332 Sgr and V1309 Sco are spatially resolved and appear bipolar. The kinematic distances to V1309 Sco and V4332 Sgr are 2.1 and 4.2 kpc, respectively. The kinetic energy stored in the ejecta of the two older red-nova remnants of V838 Mon and V4332 Sgr is of order $10^{46}$ erg, similar to values found for some post-AGB (pre-PN) objects whose bipolar ejecta were also formed in a short-duration eruption. Our observations strengthen the link between these post-AGB objects and red novae and support the hypothesis that some of the post-AGB objects were formed in a common-envelope ejection event or its most catastrophic outcome, a merger.