I was able to get it to work!
You need to move 'scheme' from 'options' to 'default':
My working config:
'redis' => [
    'client' => 'predis',
    'cluster' => env('REDIS_CLUSTER', false),
    'default' => [
        'scheme' => 'tls',
        'host' => env('REDIS_HOST', 'localhost'),
        'password' => env('REDIS_PASSWORD', null),
        'port' => env('REDIS_PORT', 6379),
        'database' => 0,
    ],
    'options' => [
        'parameters' => ['password' => env('REDIS_PASSWORD', null)],
    ],
],
Note: I had also removed the 'cluster' option from 'options', but I don't suspect this to be the make-or-break with this problem.
In my final-final config, I changed it to: 'scheme' => env('REDIS_SCHEME', 'tcp'), and then defined REDIS_SCHEME=tls in my env file instead.
Tested with AWS ElastiCache with TLS enabled.
Edit:
The above config only works with single-node redis. If you happen to enable clustering and TLS then you'll need a different config entirely.
'redis' => [
        'client' => 'predis',
        'cluster' => env('REDIS_CLUSTER', false),
        // Note! for single redis nodes, the default is defined here.
        // keeping it here for clusters will actually prevent the cluster config
        // from being used, it'll assume single node only.
        //'default' => [
        //    ...
        //],
        // #pro-tip, you can use the Cluster config even for single instances!
        'clusters' => [
            'default' => [
                [
                    'scheme'   => env('REDIS_SCHEME', 'tcp'),
                    'host'     => env('REDIS_HOST', 'localhost'),
                    'password' => env('REDIS_PASSWORD', null),
                    'port'     => env('REDIS_PORT', 6379),
                    'database' => env('REDIS_DATABASE', 0),
                ],
            ],
            'options' => [ // Clustering specific options
                'cluster' => 'redis', // This tells Redis Client lib to follow redirects (from cluster)
            ]
        ],
        'options' => [
            'parameters' => [ // Parameters provide defaults for the Connection Factory
                'password' => env('REDIS_PASSWORD', null), // Redirects need PW for the other nodes
                'scheme'   => env('REDIS_SCHEME', 'tcp'),  // Redirects also must match scheme
            ],
        ]
    ]
Explaining the above:
'client' => 'predis': This specifies the PHP Library Redis driver to use (predis). 
'cluster' => 'redis': This tells Predis to assume server-side clustering. Which just means "follow redirects" (e.g. -MOVED responses). When running with a cluster, a node will respond with a -MOVED to the node that you must ask for a specific key. 
- If you don't have this enabled with Redis Clusters, Laravel will throw a 
-MOVED exception 1/n times, n being the number of nodes in Redis cluster (it'll get lucky and ask the right node every once in awhile) 
'clusters' => [...] : Specifies a list of nodes, but setting just a 'default' and pointing it to the AWS 'Configuration endpoint' will let it find any/all other nodes dynamically (recommended for Elasticache, because you don't know when nodes are comin' or goin'). 
'options': For Laravel, can be specified at the top-level, cluster-level, and node option. (they get combined in Illuminate before being passed off to Predis) 
'parameters': These 'override' the default connection settings/assumptions that Predis uses for new connections. Since we set them explicitly for the 'default' connection, these aren't used. But for a cluster setup, they are critical. A 'master' node may send back a redirect (-MOVED) and unless the parameters are set for password and scheme it'll assume defaults, and that new connection to the new node will fail.