I was able to solve this using the following block:
location ~ /l/(.*)=(.*) {
rewrite ^([^=]*)=(.*)$ $scheme://$host$1-$2;
return 301;
}
This seemed to work even when there are multiple key-value pair segments in the the path, ex:
domain.com/l/color=red/size=large/shape=round
UPDATE:
I discovered that in cases where multiple key-value segments were present, there were multiple 301 redirects, and Google doesn't like this.
So I ended up going with:
location ~ /l/(.*)=(.*) {
rewrite ^([^=]*)=([^=]*)=([^=]*)=([^=]*)=([^=]*)=([^=]*)=([^=]*)=([^=]*)=(.*)$ $scheme://$host$1-$2-$3-$4-$5-$6-$7-$8-$9 permanent;
rewrite ^([^=]*)=([^=]*)=([^=]*)=([^=]*)=([^=]*)=([^=]*)=([^=]*)=(.*)$ $scheme://$host$1-$2-$3-$4-$5-$6-$7-$8 permanent;
rewrite ^([^=]*)=([^=]*)=([^=]*)=([^=]*)=([^=]*)=([^=]*)=(.*)$ $scheme://$host$1-$2-$3-$4-$5-$6-$7 permanent;
rewrite ^([^=]*)=([^=]*)=([^=]*)=([^=]*)=([^=]*)=(.*)$ $scheme://$host$1-$2-$3-$4-$5-$6 permanent;
rewrite ^([^=]*)=([^=]*)=([^=]*)=([^=]*)=(.*)$ $scheme://$host$1-$2-$3-$4-$5 permanent;
rewrite ^([^=]*)=([^=]*)=([^=]*)=(.*)$ $scheme://$host$1-$2-$3-$4 permanent;
rewrite ^([^=]*)=([^=]*)=(.*)$ $scheme://$host$1-$2-$3 permanent;
rewrite ^([^=]*)=(.*)$ $scheme://$host$1-$2 permanent;
}
The decreasing powers of 2s example (How to replace underscore to dash with Nginx) did not work for me.