Previous one didn't work, because I mixed up a0 and a1 pointers when subtracting.

But that gave me a new idea: copy pointer to d0 and complement the difference instead of addq, saving a1 register (+stack operations) and a move-instruction:

  strlen:   move.l  %a0,-(%sp)
            movl    %a0, %d0   ;# d0 = a0;
  slenloop: tst.b   (%a0)+     ;# test *a0, post incr
            bneb    slenloop   ;# loop if non-zero
            sub.l   %a0, %d0   ;# d0 = d0 - a0;
            not.l   %d0        ;# d0 = ~d0;
            move.l  (%sp)+,%a0
            rts                ;# d0 is the return value

Equivalent C-code (http://cpp.sh/2oecd):

  #include <stdio.h>
  #include <stdint.h>
  
  size_t strlen68k(char* a0) {
      int zero_flag;
      uintptr_t d0 = (uintptr_t) a0;
      do {
          // tstb (%a0)+
          if (*a0 == 0) 
              zero_flag = 1;
          else
              zero_flag = 0;
          a0++; // (%a0)+ (post increment)
      } while(!zero_flag); // bneb slenloop
      d0 = d0 - (uintptr_t) a0; // sub.l %a0, %d0
      d0 = ~d0;  // not.l %d0
      return d0;
  }
  
  void strlen_test(char* str) {
      printf("str \"%s\" length is %lu\n", str, strlen68k(str));
  }
  
  int main(void) {
      strlen_test("");
      strlen_test("a");
      strlen_test("abcd");
      return 0;
  }

Again, untested, but I think it probably works. I guess this is also faster for all string lengths >0 as well.

This idea might not work on PDP-11 anymore, depending on how binary arithmetic is implemented.