How to achieve a multi-column layout for footnotes?

you can improve it with minipages. After the sidewaystable you have to increase the footnote counter, if another footnote appears.

\documentclass{article}
\usepackage{rotating,tabularx}
\begin{document}

\begin{sidewaysfigure}
\rule{\linewidth}{5cm}\par
The package sets the\footnotemark[1] footnotes\footnotemark[2] of a single-column document in two columns; 
the package offers a range of parameters to determine\footnotemark[3] the exact appearance\footnotemark[4] of the two columns.


\vspace{1cm}
\footnoterule\footnotesize
\begin{minipage}[t]{0.49\linewidth}
\textsuperscript{1} This is the first footnote. And here comes some nonsense text
                    to show that the linebreaks works \par
\textsuperscript{2} This is the second footnote.\par
\end{minipage}\hfill
\begin{minipage}[t]{0.49\linewidth}
\textsuperscript{3} This is the third footnote. \par
\textsuperscript{4} This is the fourth footnote.\par
\textsuperscript{5} This is the fourth footnote.\par
\textsuperscript{6} This is the fourth footnote.\par
\end{minipage}
\end{sidewaysfigure}

\end{document}

Use dblfnote package:

\documentclass{article}
\usepackage{dblfnote}
\begin{document}
The package sets the footnotes of a single-column document in two columns; the package offers a range of parameters to determine the exact appearance of the two columns.
\footnote{This is the first footnote.}
The package sets the footnotes of a single-column document in two columns; the package offers a range of parameters to determine the exact appearance of the two columns.
\footnote{This is the second footnote.}
\footnote{This is the third footnote.}
The package sets the footnotes of a single-column document in two columns; the package offers a range of parameters to determine the exact appearance of the two columns.
\footnote{This is the fourth footnote.}
\footnote{This is the first footnote.}
The package sets the footnotes of a single-column document in two columns; the package offers a range of parameters to determine the exact appearance of the two columns.The package sets the footnotes of a single-column document in two columns; the package offers a range of parameters to determine the exact appearance of the two columns. \footnote{This is the second footnote.}
\footnote{This is the third footnote.}
\footnote{This is the fourth footnote.}
\footnote{This is the second footnote.}
\footnote{This is the third footnote.}
\footnote{This is the fourth footnote.} \footnote{This is the second footnote.}
\footnote{This is the third footnote.}
\footnote{This is the fourth footnote.}
\footnote{This is the second footnote.}
\footnote{This is the third footnote.}
\footnote{This is the fourth footnote.} 
\footnote{This is the second footnote.}
\footnote{This is the third footnote.}
\footnote{This is the fourth footnote.}
\footnote{This is the second footnote.}
\footnote{This is the third footnote.}
\footnote{This is the fourth footnote.}
\footnote{This is the second footnote.}
\footnote{This is the third footnote.}
\footnote{This is the fourth footnote.}
\footnote{This is the second footnote.}
\footnote{This is the third footnote.}
\footnote{This is the fourth footnote.}
\footnote{This is the second footnote.}
\footnote{This is the third footnote.}
\footnote{This is the fourth footnote.}
\footnote{This is the second footnote.}
\footnote{This is the third footnote.}
\footnote{This is the fourth footnote.}
\footnote{This is the second footnote.}
\footnote{This is the third footnote.}
\footnote{This is the fourth footnote.}
\footnote{This is the second footnote.}
\footnote{This is the third footnote.}
\footnote{This is the fourth footnote.}
\end{document}

Gives:

Sorry for my late response. I still can think of two other solutions that work in your situation and it is automatic. This is applied to Herbert's given example:

You can either use memoir class:

\documentclass{memoir}
\usepackage{rotating,tabularx}
\twocolumnfootnotes
\begin{document}
\begin{sidewaysfigure}
\rule{\linewidth}{5cm}\par
The package sets theof a single-column\footnote{This is a test.} document in two columns; 
the package offers a range of parameters\footnote{This is a test.} \footnote{This is a test.} to determinethe exact appearance of the two columns.\footnote{This is a test.}\footnote{This is a test.}\footnote{This is a test.}
\end{sidewaysfigure}
\end{document}

which gives:

or you can use ledmac package:

\documentclass{article}
\usepackage{rotating,tabularx}
\usepackage{ledmac}
\foottwocolX{A}
\begin{document}
\begin{sidewaysfigure}
\rule{\linewidth}{5cm}\par
The package sets theof a single-column\footnoteA{This is a test.} document in two columns; 
the package offers a range of parameters\footnoteA{This is a test.} \footnoteA{This is a test.} to determinethe exact appearance of the two columns.\footnoteA{This is a test.}\footnoteA{This is a test.}\footnoteA{This is a test.}
\end{sidewaysfigure}
\end{document}

Which gives: