I could swear I've read a good answer to this question on this subreddit before, but reddit and google search are failing me. Rather than break the rules and badly relay the post from memory I figured I could at least point out this post from u/restricteddata I found that was tangentially related and might be at least a little helpful.

I have waited to post this as I am just a name history enthusiast, but my two interests are surnames as first names and name genders, so hopefully this is useful and answers your question (and passes muster with r/AskHistorians, I accept that it may not).

The first clue to understanding the gender of the names you listed is that they all come from surnames. Except for a few exceptions, unisex names or names that have been popular for men and women at different times come from surnames (with place names and word names rounding out the category). The tradition of giving a relative’s or godparent’s surname as first name is not new and although they are more often given to male children, they are occasionally given to female children as well. In 1605 English antiquarian William Camden wrote in Remains Concerning Britain

“Whereas in late years Surnames have been given for Chriſtian names amongus, and no where elſe in Chriſtendome ; although many diſlike it, for that great inconvenience will enſue : nevertheleſs it ſeemeth to proceed from hearty good will, and affection of the Godfathers to ſhew their love, or from a deſire to continue and propagate their own names to ſucceeding ages.”

Early examples are often found in the British peerage and seem especially prevalent in Scotland. Surnames are by usage not gender specific so whether a surname as a first name becomes gendered really depends on whether it catches on with the general public outside the traditional honour usage in families. There are lots of reasons why a surname might become popular as a first name, but it can usually be narrowed down to the influence of a famous person or a character name in popular media.

You asked about Leslie so I’ll use that as an example. Clan Leslie is a lowland Scottish clan that was established in 1067 when a nobleman from Hungary named Bartolf built a castle at Lesselyn, which likely was Gaelic for “garden of holly” (it has also been said to mean “from the grey fort”, or other folk etymologies such as recorded in Walter Scott’s Quentin Durward where it is said to be the location of the first descendant’s great victory, the less lees). The family’s surname was taken from this place name and they have had a long history as a noble family with the title Earl of Rothes. The first notable use as a first name was in Robert Burn’s 1792 poem “Bonnie Lesley”, which is written about Miss Lesley Baillie of Ayrshire. (Source: Everyman’s Dictionary of First Names by Leslie Dunkling, 1983) This set a precedent for the -ley spelling of the name to be the female version in the UK, but not in the US. Donald Whyte puts the earliest example of Leslie for men as 1832 (Scottish Forenames: their origins and history, 1996). In 1866 an American book aimed at young girls called “A Summer in Leslie Goldthwaite’s Life” was written by A.D.T. Whitney where Leslie was a woman. It had several reissues and was printed in England as well. Leslie was also used as a man’s name in a play written by American dramatist Forbes Heermans in 1889 called “Love by Induction”. Leslie started to gain in popularity in England and Wales for boys in the 1870s with peak British popularity in 1924 when Leslie ranked 15th most popular boys name. In the US it did not get quite as popular, hovering around the top 100 names for boys (it was about 1/5th as popular). From the perspective of the 1890s, especially the US, Leslie was a unisex surname name that was trending for boys but not girls.

In the 1950 edition of E.G. Withycombe’s The Oxford Dictionary of Christian Names, Leslie is listed as both a male and female name, which would have been at the cusp of the name increasing in popularity for girls (first edition was published 1945 and I can’t check if it was listed for both then). I don’t know why it started getting popular for boys at the end of the 19th century, and even Withycombe writing in the 1940s did not suggest a possible influence.

Leslie stuck around as a popular name for boys and had some renewed interest in the 1930s and 1940s due to the influence of male Hollywood actors Leslie Banks and Leslie Howard. Leslie Howard played Ashley (a surname name) in the famous Hollywood movie about the American civil war in Gone With the Wind in 1939 (along with the other uncommon surnamed characters, Rhett, Scarlett, Brent, Stuart, and Beau, short for Beauregard). English born Howard named his daughter after himself in 1924, Leslie Ruth Howard (Ruth after her mother).

Leslie really started trending for girls after 1940 when Bette Davis starred as Leslie Crosby in the movie The Letter. This movie was based on the 1927 play of the same name which ran for 60 weeks in London, and 106 performances in New York. The next big influence on the name for girls was when French-American actress Leslie Caron made her acting debut in 1951 in the movie An American in Paris. The popularity peaked for girls in the UK in the late 1950s and in the late 1960s in the US, but only reached 64 in the rankings in the US. Humphrey Bogart named his daughter Leslie after Leslie Howard in 1952. It still ended up more popular for girls though, with there being twice as many girls named Leslie during the period of popularity for girls compared to when it was popular for boys. It was more even in the UK if you include both spellings.

People didn’t stop naming their sons Leslie at that point. It only left the US top 1000 names for boys in 1998, when it was being given to 150 boys a year, down from a high of 2300 a year in 1952. In the UK Leslie still ranked 42nd most popular boy name in 1954 when Lesley was popular for girls and ranked 19th (it was still in the top 100 boys names in 1964 too). Some famous male Leslie’s did chose stage names, such as Jimmy Young (Leslie Young) and Bob Hope (Leslie Townes Hope), but others such as Canadian born Leslie Neilson kept his throughout his career. Stage names are chosen for a long list of reasons and this change doesn’t necessarily reflect on the perceived gender of the name.

In summary, in the case of Leslie, it is a surname that had periods of popularity for both men and women as a first name. It was a new and trendy name, not an established name with a culturally agreed upon gender association, with a history of being used in media by both men and women. Because it ended up being more popular for girls, the gender perception of the name became mostly feminine (at least in the US, less so in the UK due to the segregated spelling).

Not all surnames end up that way. In the US Cody, Ryan and Kyle are all surnames that had some female usage before they grew overwhelmingly popular for boys. Ashton was at one point more popular for girls before Ashton Kutcher influenced the gender perception for boys beginning in 1999.

On the others, Ashley was very rare for either gender, both before and after Gone With the Wind. Even as it started getting increased usage for boys, it was about half as popular with girls. Before the 1984 mermaid movie Splash with Daryl Hannah, Madison was only being given to 20 or 30 boys a year (which is about as popular as Dorcas or Fanny is today for girls). They were surnames, not masculine first names like Edward or James, and were as recognizably gendered to the general population as any surname. And they weren't as a category viewed as unsuitable for women. In 1863 C.M. Yonge in History of Christian Names commented on the names Eveline and Evelyn:

” Eveline has never been frequent but was never entirely forgotten in England (for instance, an Eveline Elstove was baptized in 1539,) and was revived as an ornamental name by Miss Burney's Evelina. At present it is one of those most in vogue but it ought not to be spelt with a y unless it be intended to imitate the surname Evelyn, the old French form of the Latin avellana, a hazel.”

She doesn’t say avoid Evelyn because it’s a masculine version of the name, only make sure you know it's a surname, and the older more traditional spelling should be preferred. She does list Evelyn as a masculine name in the glossary. (Also it appears this advice was not heeded since the -lyn spelling took off after 1894 and became the most popular spelling for women.)

In conclusion, names that appear to swap genders were not both relatively common and solidly male. They are either rare names without a strong gender association, or common names that were ambiguous in gender. They can’t be compared to names like David or Matthew which are both very common names and strongly gendered and were not viewed the same way.

(Along with the quoted sources, I also need to mention that The Baby Name Wizard graphing tool linked in the above 4 year old comment has been removed, but a new one by the same author, Laura Wattenberg, can be found at https://namerology.com/baby-name-grapher/. I also use behindthename.com for American name data, and a Flourish studio demo for English names back to the 1840s here: https://demos.flourish.studio/namehistory/. The creator of this tool, Anna Powell-Smith, also made the visualizer for the more recent England and Wales baby name data 1996-2020: https://names.darkgreener.com/)