Marvin, from The Hitchiker's Guide to the Galaxy, is clearly depressed, but there are not any indications that I recall (from the books, at least ) that he is paranoid. Yet both in-universe and out-of-universe, he's very often referred to as "Marvin the paranoid android" (Wikipedia even lists this as an alternate name for the character). Why is this? Is the character in the original radio show more paranoid?
Quite simply because it rhymes.
There is no suggestion that Marvin is clinically paranoid anywhere in the series.
Zaphod Beeblebrox is the first person to use the epithet in the radio series. Also, he calls Marvin many things as the series progresses. However, it is the Paranoid Android that sticks. Most characters refer to Marvin as a Robot, not as an Android. There aren't so many snappy phrases that use the word robot.
Zaphod often uses nicknames for other characters. They aren't always good descriptions.
It might have something to do with the amount of pessimism Marvin displays. He's convinced terrible things will come of just about everything, and that people are going to treat him poorly, hence him being paranoid.
As noted there are also a number of points where he's referred to as being very depressed.
Overall though... this is Douglas we're talking about, his MO is inconsistency, contradiction and throw away jokes. I am quite comfortable accepting the notion that he went along with labelling Marvin paranoid just because it sounded nice. Need I remind people of the story behind Zaphod's third arm and second head and just how much trouble that caused when they tried to make the TV series? ;)
As mentioned before, the term comes from Zaphod. His own psych profile is "He's just zis guy". Don't expect a proper psychiatric diagnosis from him.