I just used \caption* for the second occurrence of algorithm block and it is all good now :)
\documentclass{article}
\usepackage{algpseudocode}
\usepackage{algorithm}
\begin{document}
\begin{algorithm}
\caption{Algorithm XYZ}
\label{findme}
\begin{algorithmic}[1]
\State Do Something 1
\State Do Something A
\State Do Something B
\State Do Something C
\algstore{myalg}
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\caption*{Algorithm~\ref{findme} Continue ...}
\begin{algorithmic} [1]
\algrestore{myalg}
\State Do Something D
\State Do Something E
\State Do Something F
\end{algorithmic}
\end{algorithm}
\end{document}