В общем-то раньше линолеум довольно часто стелили на битум, или укладывали плитки ПВХ.
Или же битум присутствовал в «пироге» пола, помимо битума использовали листы ДВП.
Если придерживаться правильной технологии укладки линолеума, то поверхность нужно выравнивать ноль.
Если Вы к примеру сняли старый линолеум, или паркет и под ними слой битума, то возьмите в руки уровень и проверьте пол на предмет его ровности.
Если полы не ровные, то их нужно выравнивать, можно стяжкой.
В теории в помещениях до 20 кв.м, линолеум можно крепить без клеевого слоя, то есть крепление только напольными плинтусами.
Если на Вашем битуме нет ям, бугров, поверхность идеально ровная, то можно на такой битум постелить линолеум.
Можно даже пробовать залить тонкий слой стяжки, нужна выравнивающая смесь, я покупал вот такую
«Церезит CN 88».
Плюс предварительная подготовка, битум гладкий, поверхность нужно сделать чуть шероховатой, можно загрунтовать в 2 слоя с просушкой «Бетонконтактом», или сделать самодельную грунтовку (смесь) пес ок + цемент + клей ПВА, после просушки уже заливаем выравнивающую смесь.
Стяжку можно и армировать если нужен с большой слой.
Вот это в целом, но правильней очистить пол до основания, битум можно прогреть и удалить с пола, можно дать насечку и удалять его поэтапно.
Или же сразу делать полы на лагах, если высота помещения позволяет.
Удаление битума работа пыльная, грязная, + крайне трудоёмкая, но если делать с соблюдением технологии, без удаления битума не обойтись.