É uma questão matemática não precisando de expressões condicionais ou substituições de strings. Veja seus requisitos:

> ...O primeiro "001" será incrementado em 1 quando o segundo "001" chegar
> ao valor 250, sendo que esse segundo contador será incrementado de
> acordo com o index do dataframe, e quando ele chega a 250 o seu valor
> deve retornar para o inicial "001"...

* O primeiro valor, esse pode ser calculado, a cada linha, com a [divisão inteira //][1] de cada elemento do índice por 251.

* Quanto ao segundo valor, esse pode ser calculado a cada linha com o [operador resto %][1] da divisão de cada elemento índice por 250.


Definindo `df` como um conjunto de dados para esse exercício mental:
```
>>> import pandas as pd

>>> df = pd.DataFrame({"Mobile Phone":["+XXXXXXXXXXXXX"]*1000})
#       Mobile Phone    
#0     +XXXXXXXXXXXXX  
#1     +XXXXXXXXXXXXX  
#2     +XXXXXXXXXXXXX  
#3     +XXXXXXXXXXXXX 
#...        ...
#999   +XXXXXXXXXXXXX
```

Adequando o [índice do DataFrame][2] ao exemplo da pergunta, o incrementando em uma unidade:
```
>>> df.index += 1
#       Mobile Phone    
#1     +XXXXXXXXXXXXX  
#2     +XXXXXXXXXXXXX  
#3     +XXXXXXXXXXXXX  
#4     +XXXXXXXXXXXXX 
#...        ...
#1000   +XXXXXXXXXXXXX
```

Calculando e formatando o primeiro número fazendo as devidas compensações por conta do índice incrementado. Em seguida alterando o tipo dos dados de numérico para string com [pandas.Series.astype][3] e caso necessário o preenchendo com zeros a esquerda com [pandas.Series.str.zfill][4] 

```
>>> (df.index // 251 + 1).astype(str).str.zfill(3)
#001
#001
#001
#001
...
#004
```

Calculando e formatando o segundo número fazendo as devidas compensações.
```
>>> ((df.index - 1) % 250 + 1).astype(str).str.zfill(3) 
#001
#002
#003
#004
...
#250
```

Então o calculo de `'Count Identifier'` de forma vetorizada será:
```
>>> df['Count Identifier'] = (
...    "Prefix - " + 
...    (df.index // 251 + 1).astype(str).str.zfill(3) +
...    " - " +
...    ((df.index - 1) % 250 + 1).astype(str).str.zfill(3)  
...)
>>> df
#       Mobile Phone    Count Identifier
#1     +XXXXXXXXXXXXX  Prefix - 001 - 001
#2     +XXXXXXXXXXXXX  Prefix - 001 - 002
#3     +XXXXXXXXXXXXX  Prefix - 001 - 003
#4     +XXXXXXXXXXXXX  Prefix - 001 - 004 
#...        ...               ...
#1000  +XXXXXXXXXXXXX  Prefix - 004 - 250
```

Juntando tudo num único fragmento:
```
import pandas as pd

df = pd.DataFrame({"Mobile Phone":["+XXXXXXXXXXXXX"]*1000})
df.index += 1

df['Count Identifier'] = (
    "Prefix - " + 
    (df.index // 251 + 1).astype(str).str.zfill(3) +
    " - " +
    ((df.index - 1) % 250 + 1).astype(str).str.zfill(3)    
)

print(df.to_string())   #Força a impressão de todas as linhas do dataframe.
```

<sup>Veja o resultado no [Replit][5]</sup>


  [1]: https://docs.python.org/pt-br/3/library/operator.html#mapping-operators-to-functions
  [2]: https://pandas.pydata.org/docs/reference/api/pandas.DataFrame.index.html
  [3]: https://pandas.pydata.org/docs/reference/api/pandas.Series.astype.html
  [4]: https://pandas.pydata.org/docs/reference/api/pandas.Series.str.zfill.html
  [5]: https://replit.com/@Augusto-Vasques/modcounter#main.py