C#

Part 2 was pretty much the same as Part 2 except we can't short-circuit when we find the first match. So, implement a cache of each sub-pattern and the number of ways to form it from the towels, and things get much faster.

using System.Collections.Immutable;
using System.Diagnostics;
using Common;

namespace Day19;

static class Program
{
    static void Main()
    {
        var start = Stopwatch.GetTimestamp();

        var sampleInput = ReceiveInput("sample.txt");
        var programInput = ReceiveInput("input.txt");

        Console.WriteLine($"Part 1 sample: {Part1(sampleInput)}");
        Console.WriteLine($"Part 1 input: {Part1(programInput)}");

        Console.WriteLine($"Part 2 sample: {Part2(sampleInput)}");
        Console.WriteLine($"Part 2 input: {Part2(programInput)}");

        Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
    }

    static object Part1(Input input)
    {
        return input.Patterns
            .Select(p => AnyTowelMatches(p, input.Towels) ? 1 : 0)
            .Sum();
    }

    static object Part2(Input input)
    {
        var matchCache = new Dictionary<string, long>();
        return input.Patterns
            .Select(p => CountTowelMatches(p, input.Towels, matchCache))
            .Sum();
    }

    private static bool AnyTowelMatches(
        string pattern,
        ImmutableArray<string> towels)
    {
        return towels
            .Where(t => t.Length <= pattern.Length)
            .Select(t =>
                !pattern.StartsWith(t) ? false :
                (pattern.Length == t.Length) ? true :
                AnyTowelMatches(pattern.Substring(t.Length), towels))
            .Any(r => r);
    }

    private static long CountTowelMatches(
        string pattern,
        ImmutableArray<string> towels,
        Dictionary<string, long> matchCache)
    {
        if (matchCache.TryGetValue(pattern, out var count)) return count;

        count = towels
            .Where(t => t.Length <= pattern.Length)
            .Select(t => 
                !pattern.StartsWith(t) ? 0 :
                (pattern.Length == t.Length) ? 1 :
                CountTowelMatches(pattern.Substring(t.Length), towels, matchCache))
            .Sum();

        matchCache[pattern] = count;
        return count;
    }

    static Input ReceiveInput(string file)
    {
        using var reader = new StreamReader(file);

        var towels = reader.ReadLine()!.SplitAndTrim(',').ToImmutableArray();
        var patterns = new List<string>();
        reader.ReadLine();
        var line = reader.ReadLine();
        while (line is not null)
        {
            patterns.Add(line);
            line = reader.ReadLine();
        }

        return new Input()
        {
            Towels = towels,
            Patterns = [..patterns],
        };
    }

    public class Input
    {
        public required ImmutableArray<string> Towels { get; init; }
        public required ImmutableArray<string> Patterns { get; init; }
    }
}