She left the hotel without paying the bill.
How do I tell if a particular word is a preposition or an adverb when it is attached to a verb?
Without is a preposition.
Paying is not a verb, but a verbal. The entire phrase paying the bill I believe technically functions as a noun phrase.
Without paying the bill doesn't really answer the question "How did she leave?" so it's not adverbial. Without paying the bill does not really have anything to do with the manner or way (this is what how means) in which she left - it describes an additional and separate idea (it's more of a what). She left AND she didn't pay the bill - she didn't leave in manner or way that obstructed her from paying the bill.