I have heard before that ありがとう came from the word "obrigado" in Portuguese. Is this true and is there any evidence to support this, or is it an old wives' tale?
It is false. ありがとう came from adjective ありがたい, which was ありがたし in classical Japanese and dates back much earlier than any loanwords from Portuguese appeared in Japanese.
Word ありがたし appeared in Makura no Sōshi (1002), although I hope that someone with access to large dictionaries can post earlier references. Loanwords from Portuguese in Japanese started appearing in the 16th century.
See also the comment to this answer by Dono. Honestly speaking, I think that it is better than this answer.