Before there were roads in the wilderness area, the best method of transportation was by water; and as the Leaf Lakes drain towards the Gulf of Mexico. Otter Tail Lake toward Hudson Bay by way of the Red River of the North.
The early explorer would portage from Leaf Lake to Portage Lake to Donald Lake to Pelican Bay on Otter Tail Lake and be on his way through Canada to Hudson Bay.
The first explorers through this area about 1750 were a Frenchman and an Englishman. They met with a band of Indians on the shore of "Lac de la Queue de la Outer", which translates roughly to the Lake of the Otters Tail.
This is on record in the archives of Congress, and I would think that it was called that for many years before that as the name derives from the sand bar shaped like an otter's tail where the Otter Tail River enters Otter Tail Lake (on the North East end of the lake) and now over two centuries later the otter's tail sand bar is still there.