Utility bills are forgeable paper, yes. So is any other proof short of the strong cryptographic kind, which is going to be a lot more trouble to get set up infrastructurally. Also, forging them, or theft of mail, is a notable threshold beyond "just say you live there". Generally, in my experience, proof-of-address is coupled with some other requirement to prove your identity, so a genuine-but-stolen utility bill would need to be coupled with either a forged ID or a remarkable resemblance to the actual owner.

It's not perfect, but I would say that in most cases it's better than nothing. It's a bit lacking for of subletters, but when I've needed proof-of-address, showing the signed lease has also been acceptable.

(I actually am in a month-to-month with no lease and with a roommate's name on the utility bill, so the last time I needed proof of address I needed something else. Can't now remember what it was.)