How to avoid a page break before a two-column TOC in memoir

A quick way is temporarily disabling \clearpage for the table of contents which prevents that page break:

\begingroup
\let\clearpage\relax
\tableofcontents*
\endgroup

After that group, \clearpage has the original meaning.

\documentclass[10pt,a4paper]{memoir}
\usepackage{multicol}
\makeatletter
\renewcommand\tableofcontents{%
\begin{multicols}{2}[
    \section*{\huge\contentsname
        \@mkboth{%
           \MakeUppercase\contentsname}{\MakeUppercase\contentsname}}]
    \@starttoc{toc}%
\end{multicols}}
\makeatother
\begin{document}
\frontmatter
\title{Something or other}
\author{H.I.M. Self}
\maketitle
\tableofcontents
\mainmatter
\chapter{Introduction}
\chapter{First chapter}
\section{First section}
\end{document}