The combat, though, is becoming really frustrating. At first, I thought it was just bad combat design. But now there are videos on youtube of people stringing together great combos, while every fight is taking me ten minutes or longer to whittle down their health:
After seeing this, I realized that there's a good system there, the problem is that I just don't understand how to use it. I never learned how to use the counter system properly, but now I'm 2/3 through the game, where that knowledge seems to be required to advance.
Require understanding of mechanics early
I played the tutorial at the beginning of the game, but I don't think it ever required me to specifically counter an attack, or if it did it let me squeak by with just countering one attack by luck.
In a game that's about countering and stringing together combos, the tutorial should have specifically required me to counter 5 attacks in a row before continuing, and to build up a long combo against an easy enemy.
Because the tutorial and first few bosses let me win without playing well, I find myself completely stuck in the endgame, without the necessary skills to succeed, and no way to learn them in a safe environment.
Mechanics can be too hard; tutorials can't
Don't be afraid to require players to master each isolated element of your game early on. It's important to require a player to learn the basic mechanics of your game, under controlled circumstances, before completing the tutorial. If a player can't counter 5 times in a row against an enemy that's not a threat, then you'll just find out right away that the gameplay mechanic is simply too hard.
You may encounter some players who just hate a particular game mechanic and no longer want to play your game, but it's much better for them to find that out now than 12 hours in.
Your game can be very difficult, but that difficulty should come from complex interactions between mechanics, not from an individual mechanic itself. Think of playing guitar: A music teacher will never let a student learn how to play a chord before that student has learned how to hold their instrument correctly. Good technique isn't necessary at all to play a very slow song with only one chord, but you don't want to wait to learn good technique until you're playing more difficult music and you've already developed lots of bad habits.
Make tutorials skippable, but replayable
For players who are masters at a game genre or replaying the game, it's important to let people skip the tutorial. Just make sure they can come back to it at any time, if they realize they're in over their head. Maybe even have the game watch for signs of a confused player, and remind them that they can revisit the tutorial. If your game is really slick, you can actually pepper in some easy teaching enemies and some tutorial text into the next fight, just to remind the player of the skills that they're missing.
It's certainly fine to make a gameplay element harder and harder as the game progresses, such as requiring quicker reflexes to counter or string combos together. But don't think you're doing your players any favors by "saving" them from learning the basic techniques that you'll later be requiring to move forward in the game.
Tutorials don't need to be early
If you really can't bring yourself to make the initial tutorial for your game a little more comprehensive, shake up your assumptions about when tutorials have to take place. People assume they need to only happen at the beginning of a game, but they can be placed wherever they give the player maximum benefit and minimal intimidation.
If blocking and countering don't become important until later in the game, then don't worry about teaching it in the first five minutes. But when you do decide to teach it, make sure players are actually required to learn it properly before you let them continue!