Returning entries based on Relationships across different category groups using 'and'
After some help from @RobinSchambach on the Craft Slack and a bit of trial and error I got to this, truncated for brevity.

{# clear everything #}
    {% set colourQuery = '' %}
    {% set sizeQuery = '' %}

    {# get all the search query parameters #}
    {% set colour = craft.request.getParam('colour') %}
    {% set size = craft.request.getParam('size') %}


    {% set colourQuery = colour | join(',') %}
    {% set sizeQuery = size | join(',') %}


    {# colour #}
    {% set colourParams = ['or'] %}
    {% set cats = craft.categories.group('colour').slug( colourQuery | split(',') ).find() %}
    {% for cat in cats %}
        {% set colourParams = colourParams | merge([{ targetElement: cat }]) %}
    {% endfor %}

    {# size #}
    {% set sizeParams = ['or'] %}
    {% set cats = craft.categories.group('size').slug( sizeQuery | split(',') ).find() %}
    {% for cat in cats %}
        {% set sizeParams = sizeParams | merge([{ targetElement: cat }]) %}
    {% endfor %}




    {# build criteria #}
    {% set relatedParams = ['and'] %}
    {% if colourQuery != '' %}
        {% set relatedParams = relatedParams | merge([{element : colourQuery}]) %}
    {% endif %}

    {% if sizeQuery != '' %}
        {% set relatedParams = relatedParams | merge([{element : sizeQuery}]) %}
    {% endif %}


The key difference is that I'm using the Category IDs rather than their slugs. I'm then passing them as comma delimited strings into the array to build up the criteria.

I'm working on refining this a bit more but it's now working as expected.