How is the Liar Paradox a paradox?

You are completely correct with your analysis of the statement "everything I say is false": it must be false, but this is not a paradox in the strict logical sense.

(Some people use the word "paradox", or even more frequently the adjective "paradoxical", more loosely, meaning anything that is true, though apparently false; or false, though apparently true. You could argue that the falsity of the above statement is not immediately obvious, so there may be a paradox in this sense.)

However, the term "Liar Paradox" is more usually applied to the statement "this statement is false", and this is a genuine paradox.