Completely Different Title: The title of this movie was translated as "Mr. Cat Poop" in Hong Kong. Apparently, it came from the name "Melvin", which is pronounced very similarly to the Cantonese colloquial word for cat poop.
Uma Thurman was considered for Carol, but the producers turned her down because she was too young. Melanie Griffith was offered the role, but had to turn it down due to pregnancy. Courtney Love turned down the role of Carol, as she was recording the "Celebrity Skin" album with Hole. She also felt she was too young for the part at the time.
John Cusack considered the role of Simon Bishop, but pulled out due to conflicts with writing, filming, and producing Grosse Pointe Blank. Woody Harrelson read for the part. According to Harrelson, he "went too femme on it". The audition took place at Nicholson's house and Harrelson admits that he was nervous meeting him.
The producers had Betty White in mind for the elderly neighbor, but being an animal rights activist, she was quite appalled at how the dog was treated in the story and passed.
Word of Gay: It's never mentioned, but the filmmakers decided that Frank Sachs was bisexual.