Old vinyl flooring stuck to tile
I'm picturing a felt or paper backing that has been partially dissolved and then dried out. It's probably not much different from what happens when you accidentally lay a magazine in a bit of water on your countertop at breakfast and return after work to find it glued down solid. The binders in the paper dissolve and create a weak glue.

You haven't mentioned what you've tried, but I'd start with a simple dishsoap solution. Water caused the adhesion, and water may remove it as well. A bit of soap won't hurt. 

Otherwise, I'd look at something fairly mild like wallpaper paste remover first. Harsher products are likely to damage wall finishes and grout. You could also create your own solution of white vinegar and/or lemon juice. More on that.