Well, I ended up using a heat gun. It really looks/feel like sheets of tar with a nice non sticky top layer. To scrap it I used a putting knife and "mid sized" flathead screwdriver. The putting knife had a~10cm wide, thin, and rather flexible blade. Most of the time I was rather successful heating the pad up and then sliding the putting knife under the pad an just lift the now hot and flexible tar right off the floor, leaving barely anything (there is still probably something there; I have not finished). Sometimes it would not work ( there are some areas that bump down or just felt they were not melted enough for the knife to lift it. At this times, it was better to use the screwdriver; it was also great to create "channels" with high enough edges the putting knife could come behind it and now have some purchase.

Full disclosure: I started on the floor of the passenger seat and am still about halfway done removing the pads; there were other tasks I needed to do and I switched to them so to make good use of the daylight.