One of my great pet peeves with scholars who write about the Acts of Paul is their dating of the document. Let’s start with the termini:
The terminus ante-quem is Tertullian (de Bapt.); the terminus post-quem is possibly the death of Thecla, recounted in III, 42, which recounts that she slept a beautiful sleep. We don’t know what year this was, but supposing she lived to a ripe old age, ca. 120. But the passage does not exist in Heidelberg Papyrus, and it cannot be sure that it was not added by the Seleucian cult of Thecla at the time the Acts of Paul and Thecla were detached and transmitted separately. Thus, we are left with the death of Paul under Nero. So the date of writing is between ca. AD 64 and 200.
Many recent scholars, with the notable exception of Rordorf (AD 150, EAC, 1.1122), assign a late second-century date to the Acts of Paul with little or no argumentation (Elliot, ANT, 357; Hills, Bauckham, and Marguerat in Semeia 80  pp. 146,161, 170 respectively). A date is largely assumed without criteria. I think that most scholars uncritically accept Schneemelcher’s dating, as his two vols. NTA have became a standard primer to the subject; he says (NTA 2nd ed, p. 235):
The date likewise cannot be precisely determined. We can only say that the APl must have been written before 200, the approximate date of Tertullian’s de Baptismo. Since on the other hand it is dependent on the APt, the period between 185-195 [repeated by Drobner, Fathers of the Church, p. 33; ] may be regarded as a possible estimate. An earlier dating (Rordorf) scarcely admits proof.
Well, there you go. Schneemelcher offers a single argument against Rordorf, the alleged dependence of the APl on the APt (in agreement with Schmidt,Praxeis Paulou). Yet in the SBL Seminar Papers (1992-93) and Semeia 80, this alleged dependence of the APl on APt or the AJn (Klauck, AAA, p. 50) is a subject of an unresolved (I believe, unresolvable) debate and is therefore extremely tenuous (a careful scholar, R. Gounelle places question marks besides the lines between APl on the one hand and APt, AAn AJn on the other, in his stemma of the AAA; RHPR 84  5).
I suggested an early date in my Acts of Paul and the Pauline Legacy (pp. 8-11; 199). This was first based on strong external attestation (Physiologus, Tertullian, Origen); secondly on the lack of effect of Marcionism on the text, and the charismatic activity that evidently predates Montanism (see also “The Charistmatic Gifts in the Acts of Paul“); rather it seems to be countering early heresies such as the Nicolaitans (127f.) and the follower of Saturninus (122f.). Finally the orthodoxy of the APl most strongly resemble 2 Clement, Ignatius, Polycarp and Justin (ch. 6 of Acts of Paul and the Pauline Legacy).
I want now to add the ecclesiological argument, and for me this is the most decisive. The church order in the APl seems to attest a transition between static (Onesiphorus in Iconium, Aquila in Ephesus, Stephen in Corinth, etc.) and itinerants (Paul, Demas and Hermogenes, Thecla). This most closely resembles the same period of transition that we see in the Didache (cf. Rordorf, EAC 1.1122) and Ignatius, with Ignatius apparently more advanced than Didache. For years now, I have gone to AELAC at the Bex and Dole meetings and argued that despite the lack of the term episcopos, there seems to be one leader in each locality, and I have argued that this must be the local bishop, but without the name. My French and Swiss friends have been largely unpersuaded; with the possible exception of F. Morard (who taught at the Roman Catholic Faculty in Friboug). So I give in. I accept that the bishop is not named, but that forces me to the conclusion that we are dealing with a document that was written in the transition period when itinerants and local bishops were still vying for authority, and the monoepiscopacy was not yet established. Therefore, I will propose the date to the APl in the first quarter of the Second Century, and more precisely about 100-117–a date which is somewhere between Ignatius and the Didache.
NB: Macdonald dates the APl 160-190 (Legend, 85) but gives his reasons. Pervo at the time of Trajan to Marcus (“Hard Act to Follow”–unpublished version).