NetworkManager thinks that wlp4s0 is a wired device:

May 09 11:06:06 vasilykh-thinkpad-x1 NetworkManager[302]: <info>  [1462817166.7022] manager: (lo): new Generic device (/org/freedesktop/NetworkManager/Devices/1)
May 09 11:06:06 vasilykh-thinkpad-x1 NetworkManager[302]: <info>  [1462817166.7045] rfkill1: found WiFi radio killswitch (at /sys/devices/pci0000:00/0000:00:1c.1/0000:04:00.0/ieee80211/phy0/
May 09 11:06:06 vasilykh-thinkpad-x1 NetworkManager[302]: <info>  [1462817166.7081] manager: (wlp4s0): new Ethernet device (/org/freedesktop/NetworkManager/Devices/2)
May 09 11:06:06 vasilykh-thinkpad-x1 NetworkManager[302]: <info>  [1462817166.7091] keyfile: add connection in-memory (9cdfd6b8-27b6-4a57-8c10-4e1b1181ebf1,"Wired connection 2")
May 09 11:06:06 vasilykh-thinkpad-x1 NetworkManager[302]: <info>  [1462817166.7096] settings: (wlp4s0): created default wired connection 'Wired connection 2'
May 09 11:06:06 vasilykh-thinkpad-x1 NetworkManager[302]: <info>  [1462817166.7103] device (wlp4s0): state change: unmanaged -> unavailable (reason 'managed') [10 20 2]

Probably because iwlwifi is not fully initialized at this time, it completes initialization a second later:

May 09 11:06:07 vasilykh-thinkpad-x1 kernel: Intel(R) Wireless WiFi driver for Linux
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: Copyright(c) 2003- 2015 Intel Corporation
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: iwlwifi 0000:04:00.0: Direct firmware load for iwlwifi-7265D-20.ucode failed with error -2
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: iwlwifi 0000:04:00.0: Direct firmware load for iwlwifi-7265D-19.ucode failed with error -2
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: iwlwifi 0000:04:00.0: Direct firmware load for iwlwifi-7265D-18.ucode failed with error -2
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: iwlwifi 0000:04:00.0: Direct firmware load for iwlwifi-7265D-17.ucode failed with error -2
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: iwlwifi 0000:04:00.0: loaded firmware version 16.242414.0 op_mode iwlmvm
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: usb 1-3.1.4: new full-speed USB device number 7 using xhci_hcd
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: iwlwifi 0000:04:00.0: Detected Intel(R) Dual Band Wireless AC 7265, REV=0x210
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: iwlwifi 0000:04:00.0: L1 Enabled - LTR Enabled
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: iwlwifi 0000:04:00.0: L1 Enabled - LTR Enabled
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: usbcore: registered new interface driver r8152
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: usbcore: registered new interface driver cdc_ether
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: ieee80211 phy0: Selected rate control algorithm 'iwl-mvm-rs'
May 09 11:06:07 vasilykh-thinkpad-x1 kernel: iwlwifi 0000:04:00.0 wlp4s0: renamed from wlan0

According to the log, wlp4s0 didn't even exist at the time of NM startup, so the question is why it detects it and treats as a wired interface.

Restarting NetworkManager is enough to get WiFi working.