"Legend" is defined as: 1) "A traditional story, sometimes popularly regarded to be historical but unauthenticated," and 2) "an extremely famous or notorious person, especially in a certain field."
Just from that brief definition it is evident that The Legend of Sleepy Hollow does indeed fit with the description in its title. It is a traditional story that comments on the events of the New York countryside around Tarry Town and Sleepy Hollow. There is a "city vs. country" theme that pervades the story, giving insight into some of the social themes of the day.
In addition, the definition of "myth" is "a traditional story, especially one concerning the early history of a people or explaining some natural or social phenomenon, and typically involving supernatural beings or events."
This fits obviously with the specter of the horseman, both as a historical figure from the area's past and the supernatural element typical of myth.