Great question!

Before I answer, it is helpful to understand where this idea that, as you say, "Native Americans lived more in harmony with nature," comes from. It has intellectual roots in what scholars refer to as the "noble savage" myth or the stock character of "the ecological Indian." Different iterations of this concept was developed in European and American philosophy, anthropology, poetry, plays, literature, folktales, and advertising. For example, two texts that were influential in popularizing these ideas in the United States were Ernest Thompson Seton's Two Little Savages: The Adventures of Two Boys Who Lived as Indians (1903) and Charles Eastman's The Soul of the Indian (1911). These two texts in particular exemplify what lay at the heart of noble savage myth: a Euro-American concern with the psychological, spiritual, and sociopolitical impacts of modernity. The notion that city life and civilization eroded authentic human experience, social life, virtue, and racial & sexual virility was a powerful and popular idea in late nineteenth/early twentieth century America. In my opinion, one of the most excellent scholarly works to explore this phenomenon is T.J. Jackson Lears No Place of Grace: Antimodernism and the Transformation of American Culture, 1880-1920 (1981). Philip Deloria's Playing Indian (1998) is also a worthy read.

If you are a thinking historically, it is crucial to keep this context in mind because Euro-American writings on Native American social organization, ecological practices, and property regimes were often influenced by what the authors wanted to see and the problems they were dealing with.

But your question is about history, not projection or myth. The anthropologist Shepard Krech III dealt precisely with this problem in his 1999 work The Ecological Indian: Myth and History, asking, "to what degree does the image of the Ecological Indian faithfully reflect Native North American ideas throughout time? To what extent have Native North Americans been ecologists or conservationists?" (27)

It is helpful to understand Krech's question as a response to two ways of thinking. The first is the Ecological Indian myth as I've just explained. The second is the myth's polar opposite: the idea that Native Americans had in fact quite a destructive impact on their environments. The paleobiologist Paul Martin for example, developed the "overkill hypothesis" in which he argued that Paleo-Indian hunting practices were responsible for the extinction of North American megafauna. You gestured towards this in your post but if you'd like read more, see Lisa Naggaoka, Torben Rick, and Steve Wolverton's 2018 article "The Overkill Model and its Impact on Environmental Research."

Back to Krech. While he disagrees with Paul Martin's argument, he still maintains that the Ecological Indian is indeed, a myth. The idea that Native Americans lived "in harmony" with nature suggests that they did not manipulate and change their natural environment. They irrefutably did—sometimes for better, sometimes for worse. For example:

-They depleted timber supplies by performing clearcutting to encourage grass growth for desired animals, make room for crops, and promote the growth of certain plants.

-They set fires to woodlands to gain easier access to game.

-They increased soil erosion and sediment yields.

-They overhunted both for their own sustenance and to trade/sell skins and meats.

Yet, at the same time, Native Americans also demonstrated astute conservation strategies, typically through deploying various property regimes, use-rights, sociocultural norms, and formal and informal agreements. Terry Anderson explores this in his 1996 article "Conservation Native American Style." While some have found such application of rights, territory, and property to Native American social organization contentious, the article nonetheless provides generative examples, independent of the framework we use to understand them. (Note: If you like Anderson's article, I'd recommend researching the development of the field of institutional analysis and common pool resources/CPRs. Anderson's article is part of a larger and longer debate that seeks to understand human behavior, resource use, and incentive structures. Best place to start would probably be Garret Hardin's "The Tragedy of the Commons" (1968) and then Elinor Ostrom's response in her book Governing the Commons: The Evolution of Institutions for Collective Action (1990). It's a fascinating field that has had a huge impact on studies of conservation and Native American ecological practice.)

Now, if you want a contemporary example of Native American ecological successes and failures, the historian Marsha Weiseiger explores them by examining the conflicts between New Deal conservationists and the Navajo tribe in her book Dreaming of Sheep in Navajo Country (2009). The book highlights the nuanced reality of Native American ecological practices. While early twentieth century federal agents and conservation scientists often underestimated Navajo ecological knowledge (often resulting in unilateral exercises of power that fared terribly), some Navajo nonetheless contributed to overgrazing and stock reduction, refused to acknowledge environmental degradation, and attempted to problem solve through ceremony rather than implementing changes in agricultural and husbandry practices.

This is all a long winded way so say that the Ecological Indian myth obfuscates the obvious fact that Native Americans were as prone to error as everyone else was. Sometimes they deployed resource management strategies that worked magnificently for generations. Other times they depleted plant and animal populations though unsustainable practices. Similarly, American settlers cannot be understood as a monolith that slaughtered without second thought. The historian Richard Judd posed a substantial challenge to this belief in his work Common Lands, Common People: The Origins of Conservation in Northern New England (1997) in which he explored the common resource management strategies used throughout New England municipalities (Judd chose colonial New England precisely because it is commonly associated with wanton slaughter and destruction).

This all dovetails into an even more important point: specificity is always key. The term "Native American" refers to hundreds of tribes, each with a distinctive history. Talking about generalized Native American ecological practice is in many ways more mystifying than revealing. Yet it is pervasive. Primitivists, anthropologists, environmentalists and political activists have often turned towards Native Americans as a way of critiquing their own society and yearning for a different way of living. This is not inherently wrong, we just have to be careful in making sweeping generalizations and do our best to not let our biases cloud our judgement!

Hope this helps.