FEWER
http://grammar.quickanddirtytips.com/less-versus-fewer.aspx
...GrammarGirl notes that "it is customary to use the word less to describe time, money, and distance". A limited character budget is a little like linear distance (display length of a message; "140 characters long") and a little like money (spending your allocated character count).
And, the masses have spoken:
["140 characters or less"] -> about 14,300,000 results
["140 characters or fewer"] -> about 448,000 results