Hi Yehuda,
let update the status of this issue. It's really a bug.
Starting from the hotfix 8.1.16 you can use this workaround:
var query = DocumentHelper.GetDocuments()
.Type("CMS.MenuItem", q => q.Path("/%"))
.ResultColumns(new CountColumn("NodeID").As("Count"));
In the end our developers have found that this issue is more complex and they've decided to make a wider refactoring of the code, so they decided to fix it completely for Kentico 8.2 which will be released at the beginning of January.
Best regards, Martin