TLDR: What condition should a parallel transport (assignment from paths in the base of a vector bundle to linear isomorphisms between fibers) satisfy to ensure the associated covariant derivative is linear in the tangent vector argument?
A covariant derivative $\nabla$ on a vector bundle $E\to M$ is an operator $\nabla\colon TM\times_M J^1E\to E$ satisfying a few conditions. Let $f\in C^\infty(M),$ $X\in\Gamma(TM)$ and $s\in\Gamma(E).$
- a Leibniz condition for the section: $\nabla_X(f s)=X(f)s+f\nabla_X(s)$
- a linearity condition for the tangent vector: $\nabla_{aX+bY}s = a\nabla_Xs + b\nabla_Ys$
There are other formulations of connection. One is as an Ehresmann connection, which specifies a horizontal subbundle of a fiber bundle. An Ehresmann connection is equivalent to a covariant derivative if the choice of horizontal subspace depends linearly on $s$, in a way that is described on wikipedia section on "Vector bundles and covariant derivatives" in the Ehresmann connection article. And see the related question How do connection 1-form and Ehresmann version of connections relate to each other?
Another formulation for a connection is in terms of parallel transport $\Gamma$. To each path in the base $\gamma\colon I\to M$, we assign an isomorphism of fibers $\Gamma^t_0(\gamma)\colon E_{\gamma(0)}\overset{\cong}\to E_{\gamma(t)}.$ The assignment should obey some functoriality and smoothness conditions. One expects to be able to recover the covariant derivative from the parallel transport. Indeed, the process is described on Wikipedia in the section "Recovering the connection from the parallel transport" in the parallel transport article.
Define
$$ \nabla_{\gamma}s|_{t=0}=\lim_{t\to 0}\frac{\Gamma^t_0(\gamma)^{-1}s(\gamma(t))-s(\gamma(0))}{t}. $$
Transport the neghboring vector back to the beginning fiber, take the Newton quotient there, and take the limit. From this it is easy to derive the Leibniz law for covariant derivatives.
But how do we see that $\nabla_{aX+bY} = a\nabla_X + b\nabla_Y$? Surely some additional criterion must be stipulated for $\Gamma,$ as there exist non-linear connections. Something analogous to the linearity condition for Ehresmann connections. What is this condition?
The term "linear connection" refers to linearity in the other slot. So the point here is that $\nabla_X(s_1+s_2)=\nabla_X s_1+\nabla_X s_2$. This is indeed equivalent to the parallel transport being linear as a map between fibers (and thus only makes sense on vector bundles).
What you discuss in the post is linear dependence on the direction into which you differentiate. This is not a specific feature of linear connections, it is also true for connections on general fiber bundles and indeed for arbitrary tangent maps.