Sure! Why wouldn't it be? All you need in order to have a binding contract is a mutual agreement by which each party agrees to do something in exchange for some consideration. (An example from Ohio.) Generally they don't have to be in writing at all (although written ones are easier to prove), so it shouldn't matter what you write them on.
Or what you write them in. See, e.g., "Contract Written in Blood Still Not Binding, Says Court," Lowering the Bar (Mar. 20, 2009).
This is not to say writing a contract on toilet paper would be a good idea. For one thing, the ink would bleed, which might cause problems if interpretation was needed later. Also, a pen would likely tear up the paper pretty badly, although I guess you could run the paper through a manual typewriter, if you can find one. And if this contract involved something important, you wouldn't want to leave it lying around someplace where your contract might be used for some other purpose.
The other problem, as the CBC reported this week (thanks, Tom), is that using toilet paper could be seen as disrespectful. To whom, you may be asking, and one answer is "to a hearing officer who has asked you for a copy of the retainer agreement between you and your client."
According to a decision by the Law Society of Saskatchewan (the equivalent of a state-bar ethics committee in the U.S.), such a request was made during a 2011 hearing in Prince Albert, the province's third-largest city. The adjudicator presiding over the hearing made the request so that she could rule on a request for legal fees. A court order cited in the opinion seems to require retainer agreements to be provided, but the lawyer involved took offense at this, saying that he "did not do" written retainer agreements. Oral agreements are fine in general, but oral retainer agreements between lawyer and client are a terrible idea, and in fact legal-ethics rules often require them to be in writing. That did not seem to be the case here, however.
After checking with a supervisor, the adjudicator brought this issue up again with the lawyer in a later hearing. He "became very upset and angry," questioning the adjudicator's experience, and suggested that she could tell her supervisor to "shove [his opinion about fee agreements] up his ass." Further discussion was had on the record, after which the lawyer met separately with his client.
When he returned, the adjudicator said, he "seemed kind of smug and happy." He produced a piece of paper which she saw "was a piece of toilet paper with handwriting on it." (Although the decision says a photocopy of said paper is attached, the exhibits sadly don't appear to be online.) Based on the quoted language, it looks like a perfectly good contract to me. The parties agree that the lawyer will be paid a certain amount, and both parties signed the document. But in context, the Law Society decided that the intent had been to humiliate the adjudicator (generally not a good idea), which it found to be "conduct unbecoming" a member of the legal profession.
The lawyer maintained that the incident was a "stupid joke" and said he had apologized later, but it wasn't a personal apology and so this did not sway the Law Society. It reprimanded him, fined him $500, and ordered him to pay the costs of the proceeding which it fixed at no less than $10,000. Tip: apologizing may be difficult but not apologizing can be expensive.
I think this kind of result is entirely possible in the U.S., but may be more likely in Canada. I infer that from the facts of a case the Law Society cited, in which a lawyer was reprimanded for calling another one "clueless." I guess I should be glad the rules aren't that strict down here.