They both come from the name of the drug's chemical compound, para-acetylaminophenol.

Paracetamol: Para(-a)cet(yl)am(inophen)ol

Acetaminophen: (Para-)acet(yl)aminophen(ol)

In the early 1950s, clinical trials in Britain showed that p-acetylaminophenol was safe for human consumption. Sterling-Winthrop marketed the drug as Panadol (paracetamol), with UK sales starting in 1953. Ironically, Sterling-Winthrop was an American company.

However, p-acetylaminophenol was still an unknown over the pond in the US. In 1951, the safety and efficacy of p-acetylaminophenol (based on results of British research and clinical trials) was disseminated at at an academic conference in New York City. It relieved fever and headaches as well as aspirin, without aspirin's side effects of gastrointestinal bleeding and impairments in blood clotting.

This conveniently came to the attention of Robert McNeil Jr., whose father turned a Philadelphia drugstore into a pharmaceutical giant. McNeil Jr. switched company's focus to drug manufacture after his father's death in 1933, creating McNeil Laboratories. Skip ahead to 15 years later, and McNeil Laboratories had an objective to create a prescription-only painkiller to compete with aspirin. Around the same time, Dr. James Roth, a Gastroenterologist at UPenn, held lectures warning of the dangers of aspirin, and advocated p-acetylaminophenol. Dr. Roth became a consultant for McNeil Laboratories, and the 1951 conference in New York convinced McNeil Jr. to take action. McNeil Laboratories marketed p-acetylaminophenol as acetaminophen, with the trade name of Tylenol.

Acetaminophen/paracetamol with 30mg of codeine phosphate is called Tylenol #3 in the US. It's known by various names in the UK and her realms (Panadeine, Panadol Ultra, etc.) except in Canada, where it's called Tylenol #3 like in the US.