Do I have to check if my floor is level before installing new linoleum (from a roll, not tiles)?
You likely need flat, not level.

And for that, all you really need is some sort of a long, straight edge.  A yard stick works pretty well ... just place it down anywhere you think there might be a dip or bump, and if the yard stick is flat against the floor its whole length, you're fine.

As for the implications of not having it flat, I'm not sure for linoleum.  For floating floors it's really hard to get everything to click together, and you'll end up with spots that bounce a little too much when you walk over it.  You can actually have a little imperfection, which will be mentioned on the package (eg, 1/8" over 4')

As for not having it level, things set on the ground will roll away.