The original version is at the end, this version saves the page as well as line number in the position information sp it can cope with the line number being re-set

\documentclass[letterpaper,12pt,twocolumn,landscape]{memoir}
\usepackage{polyglossia}
\usepackage[parapparatus]{eledmac}
\usepackage{lipsum}
\usepackage{verse}
\setcounter{firstlinenum}{1}
\setcounter{linenumincrement}{2}
\lineation{page}
\linenummargin{right}
\makeatletter
\def\eldefkey{\romannumeral\line@num @\romannumeral\c@page}
\let\saved@affixline@num\affixline@num
\def\affixline@num{{%
\pdfsavepos
\edef\tmp{\write\@auxout{%
\gdef\string\eldef \romannumeral\line@num @\noexpand\romannumeral\c@page
{\noexpand\the\pdflastxpos}}}%
\tmp
\expandafter\ifx\csname eldef\eldefkey\endcsname\relax
\else
\ifnum \csname eldef\eldefkey\endcsname=3818782 % 3818782
\@firstcolumntrue
\else \ifnum \csname eldef\eldefkey\endcsname=25445662 % 19514654
\@firstcolumnfalse
\else \ifnum \csname eldef\eldefkey\endcsname=5653790 % 5653790
\@firstcolumntrue
\else \ifnum \csname eldef\eldefkey\endcsname=27280670 % 21349662
\@firstcolumnfalse
\else
\showthe\line@num
\fi\fi\fi\fi
\fi
% force first number to first column
\ifnum\line@num=1
\@firstcolumntrue
\fi
\saved@affixline@num}}
\renewcommand*{\affixpstart@num}{%
\ifsidepstartnum
\if@twocolumn
\if@firstcolumn
\gdef\l@dld@ta{\llap{QQQQ{\leftpstartnum}}}%
\else
\gdef\l@drd@ta{\rlap{PPPP{\rightpstartnum}}}%
\fi
\else
\@l@dtempcntb=\line@margin
\ifnum\@l@dtempcntb>\@ne
\advance\@l@dtempcntb \page@num
\fi
\ifodd\@l@dtempcntb
\gdef\l@drd@ta{\rlap{XXXXX{\rightpstartnum}}}%
\else
\gdef\l@dld@ta{\llap{YYYYY{\leftpstartnum}}}%
\fi
\fi
\fi
}
\makeatother
\begin{document}
\chapter*{Hello World}
\beginnumbering
\pstart
\lipsum
\pend
\endnumbering
\end{document}
I didn't have the fonts so this is tested with the standard font setup, but appears to work.
Not a complete fix but a manual work-around for when things go wrong, the code added in the preamble forces the line number 30 to switch sides.
\documentclass[letterpaper,12pt,twocolumn]{memoir}
\usepackage{polyglossia}
\usepackage[parapparatus]{eledmac}
\usepackage{lipsum}
%\setmainfont{Linux Libertine O}
\linenummargin{left}
\makeatletter
\let\saved@affixline@num\affixline@num
\def\affixline@num{{%
\pdfsavepos
\edef\tmp{\write\@auxout{%
\gdef\string\eldef\romannumeral\line@num{\noexpand\the\pdflastxpos}}}%
\tmp
\expandafter\ifx\csname eldef\romannumeral\line@num\endcsname\relax
\else
\ifnum \csname eldef\romannumeral\line@num\endcsname=3818782
\@firstcolumntrue
\else \ifnum \csname eldef\romannumeral\line@num\endcsname=19514654
\@firstcolumnfalse
\else \ifnum \csname eldef\romannumeral\line@num\endcsname=5653790
\@firstcolumntrue
\else \ifnum \csname eldef\romannumeral\line@num\endcsname=21349662
\@firstcolumnfalse
\else
\showthe\line@num
\fi\fi\fi\fi
\fi
\saved@affixline@num}}
\makeatother
\begin{document}
\chapter*{Hello World}
\beginnumbering
\pstart
\lipsum
\pend
\endnumbering
\end{document}