How to change heading font style in memoir?

You can use the \markboth command to manually customize the mark (in particular, the font to be used for the mark) used in the header for a particular chapter. I don't like this approach, since it will render the document layout inconsistent (some chapters will have a header in normal size and one chapter will have a header in a smaller font).

A better option would be to use the second optional argument of the \chapter command (a feature implemented in memoir) to use a shorter text for the header; the following example illustrates these approaches:

\documentclass{memoir}
\usepackage{lipsum}

\pagestyle{headings}

\begin{document}

% using \markboth to change the mark used
\chapter{Selective printing and deleting of certain lines}
\markboth{\small \chaptername\ \thechapter. Selective printing and deleting of certain lines}{}
\section{Test section}
\lipsum[1-30]
% using the second optional argument of \chapter to change the header text
\chapter[Selective printing and deleting of certain lines][Selective action on lines]{Selective printing and deleting of certain lines}
\section{Test section}
\lipsum[1-30]

\end{document}

Use the \copypagestyle macro (memoir manual, p. 121) to clone the headings pagestyle and add a fontsize-changing macro to the default definition (which may be found at p. 124). Even better, use a shorter title for the header as suggested by Gonzalo Medina.

\documentclass[12pt]{memoir}

\makeheadrule{headings}{\textwidth}{0.3pt}

\copypagestyle{fnsizeheadings}{headings}
\makeevenhead{fnsizeheadings}{\thepage}{}{\footnotesize\slshape\leftmark}
\makeoddhead{fnsizeheadings}{\footnotesize\slshape\rightmark}{}{\thepage}

\usepackage{lipsum}

\begin{document}

\pagestyle{fnsizeheadings}

\chapter{Selective printing and deleting of certain lines}

\section{foo}

\lipsum[1-8]

\cleardoublepage
\pagestyle{headings}

\chapter[Selective printing and deleting]{Selective printing and deleting of certain lines}

\section{foo}

\lipsum[1-8]

\end{document}

A third thing to do is not to use pure capitals in the header, they take up a lot of space.

Simply issue

\nouppercaseheads

before activating the page style will deactivate the automatic upper casing