I reproduced the error (in a simpler example), and I find it impossible to find a SortExpression that would sort by the children’s score.
I saw two important additional data:
- The exception you selected when you clicked on the column heading is 
EntitySqlException - The last method in the stack trace, which ultimately throws an exception: 
EntityDataSourceView.ExecuteSelect(DataSourceSelectArguments arguments) 
ExecuteSelect is an abstract DataSourceView method that is overridden by various control elements of the data source to do the actual work of loading data from the data warehouse. In the case of EntityDataSource corresponding view is EntityDataSourceView and from the exception throw - a EntitySqlException - I would conclude that ExecuteSelect constructing the query using Entity SQL .
The DataSourceSelectArguments argument contains the parameters defined in the EntityDateSource as well as the SortExpression , which is most likely just the sort expression you specify in the TemplateField . They are used to compose the final query in Entity SQL.
I would suggest that SortExpression simply passed as an ORDER BY in an Entity SQL statement. It will look like this:
 ORDER BY Children.Count 
But this is not valid Entity SQL. You can use dotted paths to refer to navigation, but you cannot use any “LINQ-like” methods or properties (like Count ) of the navigation collection in Entity SQL.
You can write a valid SQL query, sort by the number of children. According to this example (search in "Order By - Related Entities" in the file) the correct Entity SQL statement is:
 "SELECT VALUE p2.p FROM (SELECT p, ANYELEMENT(SELECT VALUE Count(c.ChildId) FROM p.Children AS c) AS childCount FROM Parents AS p) AS p2 ORDER BY p2.childCount" 
(It's so hard to read that I don’t even know how to reverse the code semantically correct.)
I think this ANYELEMENT(SELECT... construct ANYELEMENT(SELECT... is the "subquery" in question, and wants to have in order to count the elements of the children's collection.
Obviously, you cannot pass p2.childCount to SortExpression without the entire subquery that defines p2 .
My conclusion: there is no hope of finding a working SortExpression for counting children.
Perhaps there is a way without using SortExpression - for example, by catching a click event on the header, and then building the complete request manually in the event handler, but I really don't know if and how it is possible.
Why should consumers of EntityDataSource and GridView figure this out themselves? You have seen somewhere documented: "When the data source is of type EntityDataSource , the SortExpression TemplateField in the GridView must be a valid Entity SQL ORDER BY ." I haven't done that. Just something like: " SortExpression is an expression for sorting."
Unfortunately, since nowhere is it clear what is happening with SortExpression , what is the correct syntax and which expressions are supported or not, this answer is more of an assumption than an answer.