How to merge two C# Lambda Expressions without an invoke?

The most elegant way is to use an Expression Visitor. In particular, this MSDN Blog Entry describes how to use it to combine predicates (using boolean And or Or) without Invoke.

EDITED Having realized boolean combination is not what you wanted, I wrote a sample usage of ExpressionVisitor that solves for your particular problem:

public class ParameterToMemberExpressionRebinder : ExpressionVisitor
{
    ParameterExpression _paramExpr;
    MemberExpression _memberExpr;

    ParameterToMemberExpressionRebinder(ParameterExpression paramExpr, MemberExpression memberExpr) 
    {
        _paramExpr = paramExpr;
        _memberExpr = memberExpr;
    }

    protected override Expression Visit(Expression p)
    {
        return base.Visit(p == _paramExpr ? _memberExpr : p);
    }

    public static Expression<Func<T, bool>> CombinePropertySelectorWithPredicate<T, T2>(
        Expression<Func<T, T2>> propertySelector,
        Expression<Func<T2, bool>> propertyPredicate)
    {
        var memberExpression = propertySelector.Body as MemberExpression;

        if (memberExpression == null)
        {
            throw new ArgumentException("propertySelector");
        }

        var expr = Expression.Lambda<Func<T, bool>>(propertyPredicate.Body, propertySelector.Parameters);
        var rebinder = new ParameterToMemberExpressionRebinder(propertyPredicate.Parameters[0], memberExpression);
        expr = (Expression<Func<T, bool>>)rebinder.Visit(expr);

        return expr;
    }

    class OrderLine
    {
    }

    class Order
    {
        public List<OrderLine> Lines;
    }

    static void test()
    {
        Expression<Func<Order, List<OrderLine>>> selectOrderLines = o => o.Lines;
        Expression<Func<List<OrderLine>, Boolean>> validateOrderLines = lines => lines.Count > 0;
        var validateOrder = ParameterToMemberExpressionRebinder.CombinePropertySelectorWithPredicate(selectOrderLines, validateOrderLines);

        // validateOrder: {o => (o.Lines.Count > 0)}
    }
}

This extension works:

public static class Utility
    {
        public static Expression<T> Compose<T>(this Expression<T> first, Expression<T> second, Func<Expression, Expression, Expression> merge)
        {
            // build parameter map (from parameters of second to parameters of first)
            var map = first.Parameters.Select((f, i) => new { f, s = second.Parameters[i] }).ToDictionary(p => p.s, p => p.f);

            // replace parameters in the second lambda expression with parameters from the first
            var secondBody = ParameterRebinder.ReplaceParameters(map, second.Body);

            // apply composition of lambda expression bodies to parameters from the first expression 
            return Expression.Lambda<T>(merge(first.Body, secondBody), first.Parameters);
        }

        public static Expression<Func<T, bool>> And<T>(this Expression<Func<T, bool>> first, Expression<Func<T, bool>> second)
        {
            return first.Compose(second, Expression.And);
        }

        public static Expression<Func<T, bool>> Or<T>(this Expression<Func<T, bool>> first, Expression<Func<T, bool>> second)
        {
            return first.Compose(second, Expression.Or);
        }
    }

Sample using:

Expression<Func<Product, bool>> filter1 = p => a.ProductId == 1;
Expression<Func<Product, bool>> filter2 = p => a.Text.StartWith("test");
Expression<Func<Product, bool>> filterCombined = filter1.And(filter2);