Mostly for curiosities sake: when was the earliest documented tale of Sasquatch told by the native Americans? Would that be during the 1850’s?
What you can expect to find are "Europeans" interested in native Americans and who recorded their life, style, legends, culture in books. Most of them are starting around the 1800 era (conquest of the west roughly).
Let's give an example. A considerably interesting book is Wandering of an artist among the Indians of North America by Paul Kane. It is an incredibly good book for anyone into native Americans culture mostly because vastly detailed and by someone not too biased and also not a novel. He is describing a specific creature in the Mount St Helen area (book written in 1859 but from a voyage of 1847):
When we arrived at the mouth of the Kattlepoutal River, twenty-six miles from Fort Vancouver, I stopped to make a sketch of the volcano, Mount St. Helen's, distant, I suppose, about thirty or forty miles. This mountain has never been visited by either Whites or Indians; the latter assert that it is inhabited by a race of beings of a different species, who are cannibals, and whom they hold in great dread; they also say that there is a lake at its base with a very extraordinary kind of fish in it, with a head more resembling that of a bear than any other animal. These superstitions are taken from the statement of a man who, they say, went to the mountain with another, and escaped the fate of his companion, who was eaten by the " Skoocooms," or evil genii. I offered a considerable bribe to any Indian who would accompany me in its exploration, but could not find one hardy enough to venture.
That is the kind of things you can expect to find in fairly early records. Nothing too sasquatchy or wendigoy, what we call sasquatch or wendigo are more recent creature generally from the 1930 era. But they are to the native Amerian what the castle of Bran is for Dracula.
You can see a fairly similar question about the Wendigo here.