Here's an observation about a possible minimal counterexample. Suppose one has an epimorphism $\varphi:G\times G\twoheadrightarrow H\times H$. Then we have two maps $\varphi_1:G\to H\times H$ such that $\varphi_1(g)=\varphi(g,1)$, and $\varphi_2: G\to H\times H$ such that $\varphi_2(g)=\varphi(1,g)$. We then have $\varphi(g_1,g_2)=\varphi_1(g_1)\cdot \varphi_2(g_2)$. Then clearly $ker(\varphi_1)\times ker(\varphi_2) \subset ker(\varphi)$. So $(ker(\varphi_1)\cap ker(\varphi_2) )\times (ker(\varphi_1)\cap ker(\varphi_2) ) \subset ker(\varphi)$. Let $G'=G/(ker(\varphi_1)\cap ker(\varphi_2) )$. Then the map $\varphi$ factors through the map $G\times G \to G'\times G'$. Clearly then if $G$ does not admit a surjection to $H$, then neither does $G'$. So for a minimal counterexample, we must have $ker(\varphi_1)\cap ker(\varphi_2)=1$. 

This gives some insight to a minimal possible counterexample. Consider the map $\varphi_1\times \varphi_2: G \to H\times H\times H\times H$. Then $ker(\varphi_1\times \varphi_2)=ker(\varphi_1)\cap ker(\varphi_2)=1$, so we have an embedding $G\hookrightarrow H^4$. So a minimal counterexample $G$ must embed in $H^4$.