How to typeset two verse environments side by side

There are a number of options to do what you want. One possibility would be to use minipages; the width for each minipage will be given by the corresponding \versewidth (+1pt, since \versewidth alone doesn't work).

\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{verse}

\begin{document}

\settowidth{\versewidth}{Men - kan jag ej bli älskad, jag}
\begin{minipage}[t]{\dimexpr\versewidth+1pt\relax}
\begin{verse}[\versewidth]
  Mitt hjärta, stilla dina slag, \\
  sen andra hjärtan slutits till! \\
  Men - kan jag ej bli älskad, jag \\
  \vin dock älska vill.
\end{verse}
\end{minipage}\hfill
\settowidth{\versewidth}{'T is time this heart should be unmoved,}%
\begin{minipage}[t]{\dimexpr\versewidth+1pt\relax}
\begin{verse}[\versewidth]
  'T is time this heart should be unmoved, \\
  \vin Since others it hath ceased to move: \\
  Yet, though I cannot be beloved, \\
  \vin\vin Still let me love!
\end{verse}
\end{minipage}\bigskip

From this part we can see that bla bla bla \dots

\end{document}

\begin{center}
\settowidth{\versewidth}{Men - kan jag ej bli älskad, jag}
\begin{minipage}[t]{\dimexpr\versewidth+1sp\relax}
\begin{verse}[\versewidth]
  Mitt hjärta, stilla dina slag, \\
  sen andra hjärtan slutits till! \\
  Men - kan jag ej bli älskad, jag \\
  \vin dock älska vill.
\end{verse}
\end{minipage}\hfill
\settowidth{\versewidth}{'T is time this heart should be unmoved,}
\begin{minipage}[t]{\dimexpr\versewidth+1sp\relax}
\begin{verse}[\versewidth]
  'T is time this heart should be unmoved, \\
  \vin Since others it hath ceased to move: \\
  Yet, though I cannot be beloved, \\
  \vin \vin Still let me love!
\end{verse}
\end{minipage}
\end{center}

Strangely enough, \begin{minipage}[t]{\versewidth} is not sufficient.

It's best to set \versewidth to the maximum verse length.