You could typeset the song inside a \savebox first using one column mode and measure the resulting size. If it is too large it is typeset again in two column mode. There are no packages for this as far as I know, but this could be programmed easily enough. You can collect the environment content using e.g. the environ package.
Here an example implementation using environ and multicol. Adjust it to your needs. I included two example usages with dummy text.
\documentclass{article}
\usepackage{environ}
\usepackage{multicol}
\newsavebox{\songbox}
\NewEnviron{song}{% can also have arguments
\clearpage
% Add song title, at as argument etc.
%
% The content is \BODY
% Let's save it in normal single column mode:
\savebox{\songbox}{%
\begin{minipage}{\linewidth}%
\BODY
\end{minipage}%
}%
% To high? (Replace \textheight if required)
% \ht = hight, \dp = depth, both together is the total height
\ifnum\dimexpr\ht\songbox+\dp\songbox > \textheight
% Typeset again in two column mode:
\begin{multicols}{2}%
\BODY
\end{multicols}%
\else
% Size is already OK, so use the content of the saved box:
\usebox{\songbox}%
\fi
}
\begin{document}
\begin{song}
A short song\\
La la la la la \\
A very short song indeed\\
But this is a very long line to demonstrate that we are still in single column mode. In fact it is so long that it will be broken into two lines.
\end{song}
\begin{song}
This is a long song\\
This is a long song\\
And this is a long line to show the two column mode.
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
This is a long song\\
\end{song}
\end{document}
