I definitively got over 50 before E5. In fact I think I reached 50 shortly after arriving on Poni Island. Note that this is a play-through with what I believe to be a normal amount of backtracking: I only backtracked to pick up rare battle items and TMs.
To do a quick math, there are
14 cells + 2 cores on Melemele, 3 are day exclusive, 3 are night exclusive;
18 +1 on Akala, 4 day exclusive, 4 night exclusive;
30 +1 on Ula'ula, 7 day, 7 night;
5 + 0 on Aether, 1 day, 1 night.
Suppose that you only play during a fix time each day (say nighttime only), which means that you are not getting any of the day exclusive cells (or night, if you play Moon), then you should have
13 Melemele + 19 Akala + 24 Ula'ula = 56 cells and cores, which is plenty.
Note that a few of the cells requires sharpedo, which is fine given the truck comes after. Some of them might require machamp, but I think that for cells pre-poni that's very very rare.
Pre-Poni Machamp cells I think is 2 (I know for sure Lush Jungle is post-Machamp). Meanwhile, I wasn't adverse to going off the beaten path, but I did very limited backtracking. The only backtracking I did was to get the cores at your house and in Iki Town (I did mention somewhat linearly, after all).
In my initial playthrough, I did full backtracking and got ~65 cells by E4.
So the question is: how much backtracking is considered normal or efficient? In an efficient run, do we need any backtracking? Did we even need any backtracking to Melemele other than to pick up cells? (Just looked, only two reasonably crucial TMs need backtracking: Rock Slide and maybe Thief, the latter of which you can backtrack for before you leave Melemele). And I don't think there are any critical battle items that you actually need via backtracking, considering I wasn't missing them. I had Expert Belt, Muscle Band, and an Amulet Coin which can pretty easily power your journey without the need to backtrack. While you can argue X items, you can also buy them faster and with some ease if you use the amulet coin wisely.
Caterpie / Butterfree need a much higher placement than mid. 395 BST is very weak for endgame, but in the early game it is monsterously stronger than the competition.
The moveset of Sleep Powder / Gust / Silver Wind / Psybeam is incredibly potent at early / mid game, utterly crushing every Team Skull battle single-handedly. 4x Resisting Grand Trial #1 (Fighting Types) is a bonus.
By level 30 or so, your moveset upgrades to Sleep Powder / Psychic / Bug Buzz / Gust, and by level 41 you reach the endgame of Air Slash. Now you crush Grand Trail #2 (Dark Types) with Bug Buzz. If you're slightly overleveled, Butterfree will OHKO Salazzle with Psychic (Plumeria and Totem match)... so don't worry about that STAB Flame Burst.
Boss Guzma is always owned by Butterfree. Sucker-puch can eat 90+% accurate Sleep Powder (Thanks CompoundEyes), and the rest of his Bug Pokemon can take Gust (early game) and Air Slash (late game).
On occasion, you will swap out Psychic for Shadow Ball. Its just a TM, so you can do it anytime between battles. (Ex: Shadow Ball for Elite Four Ghost fight, then swap back to Psychic for the Elite Four Fighting-type fight).
Aether Foundation is not quite as one-sided, but Bug Buzz the Psychic Types is great. There are random rock attacks on pokemon you wouldn't expect (ex: Mismagius's Power Gem), and Butterfree doesn't like that.
After that, Butterfree plays more of a utility role as you enter the final island and battle the Elite Four. Its still one of the fastest high-accuracy sleep users available in-game thanks to Sleep Powder + Compound Eyes, which is useful for post-game catching and cheesing a few battles with X Sp. Attack / X Speed.
While being outclassed doesn't equate to lowering a tier, I am going to make a comparison to see how well Butterfree does compared to something available at the same time with similar typing: Toucannon.
Butterfree:
Trial 1: No advantage
Hala: wins
Wishiwashi: No advantage
Salazzle: While you have SE psybeam, I still do not like the idea of matching it v something faster with its own STAB SE attack. Unreliable
Lurantis: 50/50. If Castform is summoned you lose thanks to Synthesis spam while Castform Weather Balls you to death. Unreliable (Immune to Sleep Powder)
Olivia: Outright lose
Vikavolt: Lose, unless you get lucky with sleep turns
Mimikyu: Who knows. You can sleep Mimikyu, but you have to depend on it not waking upon the turn you break its Disguise. If it does, you get counterslept thanks to summon Hypnosis.
Guzma: I guess it's a win with Sleep Powder.
Nanu: can win
Lusamine: a mess for everyone
Hapu: Probably lose.
Kommo'o: Turn 1 protect to summon a helper spells disaster for Butterfree.
E4: Win 1, lose 2, even matchup 1
Toucannon
Trial 1: Access to Brick Break swings this in his favor.
Hala: Wins
Wishwashi No advantage
Salazzle: about the same as Butterfree. While no SE attack, doesn't take SE damage.
Lurantis: Has a better advantage than Butterfree, as no weakness to summons.
Olivia: lose
Vikavolt: 50/50. Has SE coverage for this battle which Butterfree lacks.
Mimikyuu: Z-Steel Wing gives you a direct edge, if you can get lucky with Haunter Hypnosis.
Guzma: Win
Nanu: Brick Break wins
Hapu: SE coverage again
Kommo'o: Wins regardless.
E4: Win 1, lose 1, even 2
Butterfree is ultimately a one trick pony relying on hax. Over the course of a run, you can count on getting min sleep rolls often enough that you lose Butterfree consistently even with optimal play. Mid Tier sounds right, even with the utility offered, which many high tier mons provide as well, but with even better offensive utility.