Code that does things like strcat(strcat(strcat(strcpy(...), ...), ...), ...)

If I understand the implementation section of the proposal correctly, the preprocessor will just add ome cast to (const char*) per function call (assuming the innermost argument is const). Nothing exponential

For the ease of discussion here is the relevant piece of code:

    #define IS_POINTER_CONST(P) _Generic(1 ? (P) : (void *)(P)  \
        , void const *: 1                                       \
        , default : 0)
    #define STATIC_IF(P, T, E) _Generic (&(char [!!(P) + 1]) {0}  \
        , char (*) [2] : T                                        \
        , char (*) [1] : E)
    #define _STRING_SEARCH_QP(T, F, S, ...)       \
        STATIC_IF (IS_POINTER_CONST ((S))         \
            , (T const *) (F) ((S), __VA_ARGS__)  \
            , (T *) (F) ((S), __VA_ARGS__))

    #define memchr(S, C, N) _STRING_SEARCH_QP(void, memchr, (S), (C), (N))
    #define strchr(S, C) _STRING_SEARCH_QP(char, strchr, (S), (C))
    #define strpbrk(S1, S2) _STRING_SEARCH_QP(char, strpbrk, (S1), (S2))
    #define strrchr(S, C) _STRING_SEARCH_QP(char, strrchr, (S), (C))
    #define strstr(S1, S2) _STRING_SEARCH_QP(char, strstr, (S1), (S2))

Here `IS_POINTER_COST` expands `P` twice so `_STRING_SEARCH_QP` expands `T`, `F`, `S` and each variadic argument 2, 2, 4 and 2 times respectively. Note that only `S` and variadic arguments are expressions and evaluated only once, but the number of expanded tokens can blow up exponentially.