Belichick. Parcells. Shula. Popovich. Sather. Jackson. Torre. Coach K. Wooden. Pat Summit. What makes a long tenured coach?
Success
It needs a patient GM/team owner, since coaches like Belichick, Landry, Jimmy Johnson, etc. didn’t have success quickly. And guys like Popivich had luck like instantly finding a Tim Duncan.
Success is certainly the primary thing; if a coach isn’t consistently winning, he (or she) won’t be allowed to stay for long.
Also, in most cases, at least at the pro level, long-tenured coaches are invested with a lot of power in off-field decisions (such as personnel management and player acquisition), roles that are usually handled by a GM in most teams. These coaches either (a) formally hold the GM title, (b) have an exceptionally strong, collaborative relationship with the GM, or © effectively act in the GM role, even if the team has a separate GM.
Similarly, I’d also posit that long-tenured coaches work under owners who aren’t particularly meddlesome.
Successful coaches tend to have big egos (that’s not just a coaching thing; that’s true of most driven, successful professionals). If they find themselves in a position in which they aren’t the clear leader of their teams, they tend to move on. Mike Holmgren left the Packers in large part because he wanted to be GM as well as coach, and team management wouldn’t give him that power. Jimmy Johnson left the Cowboys because of his ongoing power struggle with Jerry Jones.
(I’m also not sure about putting Parcells on the list. Yes, he had eight seasons with the Giants, but that’s not tremendously long-tenured, compared to the other coaches on the OP’s list.)
Baseball - Connie Mack was manager of the Philadelphia (which later became Kansas City and then Oakland) Athletics for 50 years. Some good years; some bad ones.
It helps when you own the team. 
Belichick won a Super Bowl in his second season coaching the Pats, and two more in the next three years. His lack of success in his earlier career with the Browns doesn’t really weigh into his longevity with the Pats.
Jimmy Johnson isn’t really a guy I think of as a long-tenured coach. He only spent about four years apiece with each of his head coaching gigs. His successes are perhaps more impressive because of how little time he had in each of his ports of call to make them.
Tom Landry is definitely an oddball: the Cowboys were pretty miserable for the entirety of his first contract with the Cowboys. Clint Murchison’s decision to give him another contract isn’t one that would be repeated today without the coach having secret pictures of the owner with some barnyard animals.
The ultimate example of power consolidated in one person. 
See also: George Halas, Curly Lambeau, and Paul Brown.
The coach asked fans “Will you still love me if I don’t win?” fans said “Sure, and we will miss you too.”
I’d say it’s not just success, but consistent success to the degree where owners/athletic directors are willing to let a coach stay around after a few mediocre seasons in recognition that he’ll probably bounce back to the usual standard.
Someone like a Gary Patterson has had his occasional 4-8 season or 6-7 season in his 20 years at TCU, but on average his teams go around 9-3.
Sometimes though, that’s not enough; Mack Brown was let go from UT despite having ONE season worse than 8-5 in 15 years of coaching UT football. So there’s a certain element of public and/or athletic director/regent confidence involved, even if the numbers look good.
Ivy league teams will keep coaches for a while if they don’t win but after a lot of losing years they still fire guys.