Problem with counter and \pause

Solution 0: if you can live with splitting off the initial definition:

\documentclass{beamer}

\makeatletter
\newcommand\countable[1]{%
  \newcounter{cnt#1}%
  \resetcounteronoverlays{cnt#1}%
}
\newcommand{\countslides}[1]{%
  \stepcounter{cnt#1}%
  {~\footnotesize (\arabic{cnt#1})}%
}
\makeatother
\begin{document}


\countable{abc}
\begin{frame}
\frametitle{Hello \countslides{abc}}
A
\pause
B
\end{frame}

\begin{frame}
\frametitle{Bye \countslides{abc}}
C
\pause
D
\end{frame}

\end{document}

A solution that strikes me as somewhat cleaner would be this: you give the frames in question the contgroup=... key, and they should all behave as if they were broken automatically, i.e. the normal continuation title templates are applied.

\documentclass{beamer}

\makeatletter

\newcommand\handlecontgroup[1]{%
  \only<1>{%
    \ifcsname ums@cntgroup@#1\endcsname
      \relax
    \else
      \expandafter\gdef\csname ums@cntgroup@#1\endcsname{0}%
    \fi
    \beamer@autobreakcount=\csname ums@cntgroup@#1\endcsname\relax
    \advance\beamer@autobreakcount by 1\relax
    \expandafter\xdef\csname ums@cntgroup@#1\endcsname{%
      \the\beamer@autobreakcount}%
  }%
}
\define@key{beamerframe}{contgroup}{\handlecontgroup{#1}}%
\makeatother
\begin{document}


\begin{frame}[contgroup=abc]
\frametitle{Hello}
A
\pause
B
\end{frame}

\begin{frame}[contgroup=abc]
\frametitle{Bye}
C
\pause
D
\end{frame}

\begin{frame}
\frametitle{Bye}
C
\pause
D
\end{frame}

\begin{frame}[contgroup=abc]
\frametitle{Bye}
C
\pause
D
\end{frame}

\end{document}