in modern terms, if you say someone is a legend he might exist or might not - David Beckham is a legend, but so is Robin Hood.
If you say someone or something is mythical, you're saying it doesn't exist - the illuminati are a myth. You could say Robin Hood was a myth, but only if you're insisting he never existed.