I've read about Tully being used as a nickname for Petula. Patty is a sweet nickname and Patti, Pattie and Patsy could be used as well. I think "Tula" (pronounced TYOO-la or TOO-la) could work for a nickname.
There are a couple dozen records of American Petulas in the 19th century that I've found on FamilySearch. That said, Petula Clark helped popularise the name, first in Britain from 1943 and then in America from 1965.