Probably too late for helping now, but... any DIY store (at least here in the U.S.) will have a liquid wall paper remover solution. Usually, it's meant to be added to very warm water at about 50/50. Use a full strength solution, very warm, sprayed on the linoleum after "scoring" it with the cup shaped wall paper perforator (seen here:
http://www.amazon.com...llpaper/dp/B0002YWWJG ). It has three wheels inside that move randomly when rubbed over the wall and then leaves a series of small holes in the wall paper and works on the tiles as well. Spray the remover... wait for 30 minutes and spray again. This will separate the top or decorative part of the linoleum from its base as well as attack the adhesive. The top will scrape right off with most any tool. Spray the adhesive left and it, too, will come up...