Имею ли я право не говорить им свои данные и какой закон для этого могу предъявить?

Здравствуйте. В силу ст. 3 ФЗ  «О персональных данных» от 27.07.2006 N 152-ФЗ 

1) персональные данные — любая информация, относящаяся к прямо или косвенно определенному или определяемому физическому лицу (субъекту персональных данных);

Одна лишь фамилия не может Вас идентифицировать и не может быть персональными данными. Нельзя по одной фамилии Вас опознать, что это именно Вы. Так что нарушения тут нет.

Ст. 6 данного ФЗ указывает, что

1. Обработка персональных данных должна осуществляться с соблюдением принципов и правил, предусмотренных настоящим Федеральным законом. Обработка персональных данных допускается в следующих случаях:
5) обработка персональных данных необходима для исполнения договора, стороной которого либо выгодоприобретателем или поручителем по которому является субъект персональных данных, а также для заключения договора по инициативе субъекта персональных данных или договора, по которому субъект персональных данных будет являться выгодоприобретателем или поручителем;

Так что да, требовать Вашу фамилию они могут. 

Какие документы они обязаны предъявить, чтобы обосновать то что они законно требуют с меня мою фамилию и другие данные?

Denis

самого договора достаточно.

Какие меры можно предпринять если нарушают мои права неправомерно требуя персональные данные?

Denis

обратитесь в Роскомнадзор или прокуратуру. Но нарушении пока что не видно.

Могут ли они отказаться оказывать услугу потренироваться в спортзале если я им не скажу имя/фамилию?

Denis

могут отказать, поскольку действует ст. 421 ГК РФ также

1. Граждане и юридические лица свободны в заключении договора.
Понуждение к заключению договора не допускается, за исключением случаев, когда обязанность заключить договор предусмотрена настоящим Кодексом, законом или добровольно принятым обязательством.

Денис, добрый день.

Уточните, кто требует назвать фамилию и в какой именно момент: непосредственно при посещении на входе или при оплате услуг, или в момент начала тренировки?

Здесь нужно понимание самой ситуации, поскольку если Вы получаете разовую услугу и производите оплату за каждую тренировку — то требование назвать фамилию необходимо с целью заключения с Вами договора и в последующем при его исполнении Вашего согласия на обработку персональных данных в силу ст. 6 ФЗ «О персональных данных» не требуется

1. Обработка персональных данных должна осуществляться с соблюдением принципов и правил, предусмотренных настоящим Федеральным законом. Обработка персональных данных допускается в следующих случаях:
5) обработка персональных данных необходимадля исполнения договора, стороной которого либо выгодоприобретателем или поручителем по которому является субъект персональных данных, а также для заключения договора по инициативе субъекта персональных данных или договора, по которому субъект персональных данных будет являться выгодоприобретателем или поручителем;

В равной степени это касается и момента начала тренировки, если сотрудники спортзала проводят с Вами инструктаж по технике безопасности — ввиду того, что тут речь идет уже непосредственно об исполнении договора по оказанию услуги.