Just on a first read and my initial gut feeling, I don't think this can be fixed. The pager links (prev/next) use that article's category hierarchy to determine where to go, that part of the system isn't aware of the menu hierarchy and scenarios like this and to be honest I think trying to account for this specific thing might be asking for something too complex to maintain.

Just on a first read and my initial gut feeling, I don't think this can be fixed. The pager links (prev/next) use that article's category hierarchy to determine where to go, that part of the system isn't aware of the menu hierarchy and scenarios like this and to be honest I think trying to account for this specific thing might be asking for something too complex to maintain.

@mbabker But it does use the Menu Setting to determine the order of the navigation. If in the Menu Item I set the Article Order to alphabetic, the Prev/Next will be based on alphabetic order. If in the Menu Item I set the Article Order to "Most Recent", the Prev/Next will be based on the date. So the Menu Settings are taken into consideration for it.

OK, looking at https://github.com/joomla/joomla-cms/blob/staging/plugins/content/pagenavigation/pagenavigation.php that part is easy to do because it's changing the query's ORDER BY clause. The include subcategories part of that is where I think this becomes highly problematic because this means either a much heavier query or additional separate queries to include the categories data.

Not to mention this is a major behavioral change even if it is easier to do than I think it is. Right now the pager stays within the category, with your change you can take users to another category and this can and will break navigation on sites where this is a preferred behavior.

Right now the pager stays within the category, with your change you can take users to another category and this can and will break navigation on sites where this is a preferred behavior.

I see what you mean, you have a point. But at the same time, thinking about it, a Category Blog with the "Include Subcategories" option is pretty much the same thing in the first place. Clicking on each article will take you to different categories if they are from different child categories. So the fact that you're setting "Include Subcategories" to be ON sets you up for this behavior and I think that would be the expected result for navigation as well...

I have updated a site to Joomla 3.8.6, which has many articles across a parent category & lots of subcategories.
Have the Category Blog Menu set up as per @AndySDH initial description, yet only articles from the parent category are showing up, even though I have set Include Subcategories: All [& tried 1,2,3,4,5 levels].

@AndySDH are you still seeing this in the latest J3?

yes

This is still an issue in J4, can we update the label?