Excuse my late response,
With my experience with android devices, the Google Play Games (Pop-up that you signed into with your gmail) should have Leaderboards, Achievements, and a Cloud Storage, but that's only if the developers support it.
In this case it might be that it's only being used for Leaderboards and Achievements and not the Cloud Storage or it's not even being used, but the pop-up is being displayed.
Also, it generally won't work if you were using an apk with a different signature from the Play-Store. (Mods or Free-Apks fall into this category)
The safest thing to do would have been to register to the developers site, or their alternative way of storing accounts, in-order to save your progress, but this usually isn't possible.
The other way would have been to sync it to your Facebook as that usually never fails to store the data.
If this game didn't offer any of the two mentioned above that means all the data was stored locally on the phone and was wiped during the reformatting.
Sorry to bring only more bad news.